1095 Cars on Campus (30 分)

题目大意：给出每个车牌的进出时间，每一个in只与下一个相同号牌的out匹配，若没有匹配的in或out则被忽略,然后给出相应的询问，求某个时间段内的有多少辆车停留，并求出停留的最长时间。

思路：

1.先将所有数据读入按车牌号和时间排序。(时间化为秒)

2.两两比较，处理出合法的车牌，并用map保存每个车牌的停留总时间，记录最大值。

3.处理询问，可以预处理每个时间段车辆停留的个数(前缀和，经测试不用前缀和也不会超时)

4.最后就是遍历一遍map把相同停留时间的车牌输出即可

如果停留最长时间的车辆不唯一，按字典顺序输出，可以直接用map存，保证的字典顺序。

#include 
#include 
#include 
#include 
using namespace std;
//化时间为秒
struct node
{
	string s;
	int time,flag;
	bool operator < (const node&W)
	{	
        if(s != W.s) return s < W.s;//把相同牌号的放在一起
		return time < W.time;
	}
}e[10010];
int pre[10010];
mapmp;
int main()
{
	int n,k,maxtime = 0;
	cin >> n >> k;
	for(int i = 0; i < n; i ++)
	{    
	    char zt[10];int a,b,c;
        cin >> e[i].s;
		scanf("%d:%d:%d %s",&a,&b,&c,zt);
		e[i].time = a * 3600 + b * 60 + c;
		if(zt[0] == 'i') e[i].flag = 1;
		else e[i].flag = -1;
	}
	sort(e,e + n);
	vectorans;
	for(int i = 0 ; i < n - 1; i ++)
	{
		if(e[i].s == e[i + 1].s && e[i].flag == 1 && e[i + 1].flag == -1)
		{
			ans.push_back(e[i]),ans.push_back(e[i + 1]);
			mp[e[i].s] +=(e[i + 1].time - e[i].time);
			maxtime = max(maxtime,mp[e[i].s]);
		}
	}
	sort(ans.begin(),ans.end(),[](node a,node b)
         {
             return a.time < b.time;
         });
	for(int i = 0 ; i < ans.size(); i ++)
	{
		if(i == 0) pre[i] = ans[i].flag;
		else pre[i] = pre[i - 1] + ans[i].flag;//前缀和
	}
	int last = 0;
	while(k --)
	{
	   int a,b,c;
	   scanf("%d:%d:%d",&a,&b,&c);
	   int t = a * 3600 + b * 60 + c,cnt = 0;
	   for(int i = last; i < ans.size(); i ++)
	   {
		   if(ans[i].time > t)
		   {
			   printf("%dn",pre[i - 1]);
			   break;
		   }
		   else if (i == ans.size() - 1) printf("%dn",pre[i]);
		   last = i;
	   }
	}
	for(auto it : mp)
	{
		if(it.second == maxtime) printf("%s ",it.first.c_str());
	}
	printf("%02d:%02d:%02d",maxtime / 3600, maxtime % 3600 / 60, maxtime % 60);
	return 0;
}

1095 Cars on Campus (30 分)

C/C++/C#相关栏目本月热门文章