#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int MAXN = 2e5 + 5;
struct node
{
	int pr, t;//价值 获得时间
	bool v;//是否用过 false没用过 true用过
}tick[MAXN];

struct node2
{
	int ty, pr, t;
}d[MAXN];

string filename;
int pr[MAXN];//票价
int t[MAXN];//乘车时间
int ty[MAXN];//交通方式类别
//0 地铁 1 公交
int n = 0;
int solve1()
{
	cout << "solve1 " << filename << endl;
	//FILE* pf = freopen(filename.c_str(), "r", stdin);
	int cnt = 0, ans = 0;
	long long allloopcnt = 0;
	for (int i = 1; i <= n; i++)
	{
		long long loopcnt = 0;
		if (ty[i] == 0)//乘地铁
		{
			ans += pr[i];
			tick[++cnt].pr = pr[i];
			tick[cnt].t = t[i];
			tick[cnt].v = false;

			//printf("At %d: Got ticket {%d,%d,%d}\n", i, pr[i], t[i], 0);
		}
		else if (ty[i] == 1)//乘公交车
		{
			bool flag = false;
			for (int j = 1; j <= cnt; j++)
			{
				//printf("Searching ticket %d:\n", j);
				loopcnt++;
				if (tick[j].v || t[i] - tick[j].t > 45) continue;
				if (tick[j].pr >= pr[i])
				{
					//printf("At %d: Use ticket in %d\n", i, tick[j].t);
					flag = true;
					tick[j].v = true;
					break;
				}
			}
			if (!flag) ans += pr[i];
		}
		//printf("Loopcnt = %lld\n", loopcnt);
		allloopcnt += loopcnt;
	}
	//printf("AllLoopcnt = %lld\n", allloopcnt);
	return ans;
}

int solve2()
{
	//FILE* pf = freopen(filename.c_str(), "r", stdin);
	cout << "solve2 " << filename << endl;
	int cnt = 0, ans = 0;
	long long allloopcnt = 0;
	int accept = 1;
	for (int i = 1; i <= n; i++)
	{
		long long loopcnt = 0;
		if (ty[i] == 0)//乘地铁
		{
			ans += pr[i];
			tick[++cnt].pr = pr[i];
			tick[cnt].t = t[i];
			tick[cnt].v = false;

			//printf("At %d: Got ticket {%d,%d,%d}\n", i, pr[i], t[i], 0);
		}
		else if (ty[i] == 1)//乘公交车
		{
			bool flag = false;
			for (int j = accept; j <= cnt; j++)
			{
				//printf("Searching ticket %d:\n", j);
				loopcnt++;
				if (t[i] - tick[j].t > 45)
				{
					accept = j;
					continue;
				}
				if (tick[j].v) continue;
				if (tick[j].pr >= pr[i])
				{
					//printf("At %d: Use ticket in %d\n", i, tick[j].t);
					flag = true;
					tick[j].v = true;
					break;
				}
			}
			if (!flag) ans += pr[i];
		}
		//printf("Loopcnt = %lld\n", loopcnt);
		allloopcnt += loopcnt;
	}
	//printf("AllLoopcnt = %lld\n", allloopcnt);
	return ans;
}

bool cmp(node2 a, node2 b)
{
	return a.t < b.t;
}

void getdata(int n)
{
	cout << filename << endl;
	FILE* pf = freopen(filename.c_str(), "w", stdout);
	//cout << pf << endl;
	//cout << "wwwwwwwwww" << endl;
	for (int i = 1; i <= n; i++)
	{
		ty[i] = rand() % 2, pr[i] = rand() % 1000, t[i] = rand() % 1200000;
		d[i] = { ty[i] ,pr[i] , t[i] };
	}
	sort(d + 1, d + 1 + n, cmp);
	printf("%d\n", n);
	for (int i = 1; i <= n; i++)
	{
		printf("%d %d %d\n", d[i].ty, d[i].pr, d[i].t);
	}
	//cout << "wwwwwwwwwww" << endl;
	//fflush(pf);
	freopen("CON", "r", stdin);
	freopen("CON", "w", stdout);
	return;
}

void compare(int times,int v)
{
	printf("compare start\n");
	for (int i = 1; i <= times; i++)
	{
		filename = "Randomdata" + to_string(i) + ".in";
		getdata(v);

		FILE* pf = freopen(filename.c_str(), "r", stdin);
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d %d %d", &ty[i], &pr[i], &t[i]);
		}

		printf("Making data %s\n", filename.c_str());
		int s1 = solve1(), s2 = solve2();
		printf("s1 = %d, s2 = %d\n", s1, s2);
		//if (s1 == s2) printf("At %d: True\n", i);
		if(s1 != s2)
		{
			printf("%d != %d (in Randomdata%d.in)", s1, s2, i);
			system("pause");
		}
		putchar('\n');
	}
}

int main()
{
	int times, v;
	cin >> times >> v;
	srand(time(NULL));
	compare(times,v);
	//freopen("bus.in", "r", stdin);
	//freopen("bus.out", "w", stdout);
	//getdata(12000);
	//freopen("Randomdata.in", "r", stdin);
	//cin >> n;
	//for (int i = 1; i <= n; i++)
	//{
	//	  scanf("%d %d %d", &ty[i], &pr[i], &t[i]);
	//}
	//int s1 = solve1(), s2 = solve2();
	//if (s1 == s2) printf("True\n");
	//else
	//{
	//	printf("%d != %d\n", s1, s2);
	//}
	return 0;
}

自己生成数据 -> 暴力解决数据 -> 优化方案解决数据 -> 对拍

一条龙服务