[声明]：由于本人在使用《算法笔记》的过程中有部分题解和《算法笔记》上的解法不同，特此作为记录，同时可以提供新的思路供读者参考； 1. 题目链接：https://www.patest.cn/contests/pat-a-practise/1095 2. 解题思路： ①首先将输入的信息存储在结构体数组rec[]中，然后按照车牌号升序、时间升序排序(本题中用了C++的sort函数，用C中的qsort也没问题)； ②按排序后的记录一一扫描，找出有效的记录对：即当前记录和下一条记录车牌号相同&&该条记录状态为in，下一条记录为out；计算时间差；由于同一辆车可能有多余于一组的有效记录对，所以设置临时变量temp_time，将上面算出的时间差不断加入，并在该车辆牌号总停留时间计算结束后重新置零，用于下一车牌号计算总停留时间； ③找出最大的停留时间；(注意：最长停留时间的车牌号可能不止一辆，可以用max_id[][]二维数组记录下最长停留时间的车牌号，以便最后的输出)； ④如何计算某个查询时刻校园停车的总数？《算法笔记》提供了map的做法，这里用另一种方法：即以每条记录中的时刻(单位second) 作为下标，将某一时刻车辆进、出的数量分别存入intime[]和outtime[]数组中；从而方便最后的查询； ④注意利用好查询时间的升序，否则很容易超时； 3. AC代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct Rec{ char id[10]; //记录车牌 int s; //记录时间，单位秒(second) int status; //记录状态status=1表示 in，0表示out }rec[10010]; int intime[24*3600]={0},outtime[24*3600]={0}; //记录每一秒进出的车辆数 bool cmp(Rec a,Rec b){ if(strcmp(a.id,b.id)) return strcmp(a.id,b.id)<0; //车牌号升序 else return a.s<b.s; //时间升序 } bool cmp2(int a,int b){ return a<b; } int main(){ int N,K; scanf("%d%d",&N,&K); char temp_sta[4]; int h,m,s; for(int i=0;i<N;i++){ scanf("%s %d:%d:%d",rec[i].id,&h,&m,&s); //输入车牌号，时间 rec[i].s=3600*h+m*60+s; //将时间转换为second scanf("%s",temp_sta); if(strcmp(temp_sta,"in")==0) rec[i].status=1; //记录状态 else rec[i].status=0; } sort(rec,rec+N,cmp); //排序 int temp_time=0; //记录同一辆车停留的总时间 char max_id[10010][10];int max_time=0;int num=0; //max_id表示最长停留时间的插排号，max_time表示最长的停留时间 for(int i=0;i<N-1;i++){ //找出停留时间最长的车牌和时间 if(strcmp(rec[i].id,rec[i+1].id)) temp_time=0; //一个车牌号的查询已经完成，停留总时间归零用于下辆车停留总时间的计算 else if(rec[i].status==1&&rec[i+1].status==0){ //有效记录对 temp_time+=rec[i+1].s-rec[i].s; //计算某辆车牌号的总时间 ++intime[rec[i].s]; //该时刻进的车辆数+1 ++outtime[rec[i+1].s]; //该时刻出的车辆数+1 if(temp_time>max_time){ max_time=temp_time;num=0;//num=0相当于擦除之前的车牌记录，重新记录停留时间更长的车牌 strcpy(max_id[num++],rec[i+1].id); //记录车牌，同时num++ }else if(temp_time==max_time){ strcpy(max_id[num++],rec[i+1].id);//最长停留时间的车牌可能有大于1种 } } } //查询 int a,b,c;int qtime;int j=0;int ans=0; //j表示时间秒；ans表示要输出的答案(answer)，即停留在学校的车辆数 for(int i=0;i<K;i++){ scanf("%d:%d:%d",&a,&b,&c); qtime=a*3600+b*60+c; //查询时间，单位second while(j<=qtime){ ans+=intime[j]-outtime[j]; ++j; //由于时间升序，所以将ans,j都设置在循环外面； } printf("%d\n",ans); } for(int i=0;i<num;i++) printf("%s ",max_id[i]); //输出最长停留时间的车牌号 printf("d:d:d\n",max_time/3600,max_time%3600/60,max_time%60); //输出对应的时间，注意d的格式 }