同队列思想,但是TLE和WA,不知道哪里错误,求大佬帮忙康康
查看原帖
同队列思想,但是TLE和WA,不知道哪里错误,求大佬帮忙康康
1288168
silver_rain楼主2024/3/31 12:29
#include<iostream>
#include<map>

using namespace std;

struct info
{
	int time;
	int num;
	map<int, int> nation;
};
int main()
{
	int n;
	cin >> n;
	struct info a[n];
	int ans[n];
	int i, j;
	int fromBoat[n] = {0};//第i艘船的国籍记录从第fromBoat[i]开始记录 
	map<int, int> nationTemp;
	int thisAns = 0;;
	for(i = 0; i < n; i++)
	{
		cin >> a[i].time >> a[i].num;		
		for(j = 0; j < a[i].num; j++)
		{
			int temp;
			cin >> temp;
			auto it = a[i].nation.find(temp);
			if(it == a[i].nation.end())
				a[i].nation[temp] = 1;
			else
				a[i].nation[temp]++;
			if(nationTemp.find(temp) == nationTemp.end())
				thisAns++, nationTemp[temp] = 1;
			else
				nationTemp[temp]++;
		}
		int from = a[i].time - 86400 + 1;//包括from
		if(from < 0) from = 0;
		for(j = 0; j < i; j++) if(a[j].time >= from) break;
		fromBoat[i] = j;
		if(j != fromBoat[i - 1])
		{
			//删掉第fromBoat[i-1]到j-1艘船的国籍
			for(int k = fromBoat[i - 1]; k <= j - 1; k++)
			{
				map<int, int> thisNation = a[k].nation;
				for(auto it = thisNation.begin(); it != thisNation.end(); it++)
				{
					nationTemp[it->first] -= (it->second);
					if(nationTemp[it->first] == 0) thisAns--;
				}
			}
		}
		ans[i] = thisAns;
	}
	for(i = 0; i < n; i++)
	{
		cout << ans[i] << endl;
	}
}

比较了自己和题解,觉得思想应该都是队列,TLE应该是因为多了删掉第fromBoat[i-1]到j-1艘船的国籍的时间。但是为什么WA呢,求大佬解答(如果TLE也不是我说的原因,求大佬一块解答),蟹蟹!!!

2024/3/31 12:29
加载中...