PAT题解——1095. Cars on Campus (30)

[声明]：由于本人在使用《算法笔记》的过程中有部分题解和《算法笔记》上的解法不同，特此作为记录，同时可以提供新的思路供读者参考；

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[]; //记录车牌 
    int s;       //记录时间，单位秒(second) 
    int status;  //记录状态status=1表示 in，0表示out 
}rec[]; 
int intime[*]={},outtime[*]={}; //记录每一秒进出的车辆数 

bool cmp(Rec a,Rec b){
    if(strcmp(a.id,b.id)) return strcmp(a.id,b.id)<; //车牌号升序 
    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[]; int h,m,s; 
    for(int i=;i<N;i++){
        scanf("%s %d:%d:%d",rec[i].id,&h,&m,&s); //输入车牌号，时间 
        rec[i].s=*h+m*+s; //将时间转换为second 
        scanf("%s",temp_sta);
        if(strcmp(temp_sta,"in")==) rec[i].status=; //记录状态 
        else rec[i].status=;
    }
    sort(rec,rec+N,cmp); //排序 
    int temp_time=;  //记录同一辆车停留的总时间 
    char max_id[][];int max_time=;int num=; //max_id表示最长停留时间的插排号，max_time表示最长的停留时间 
    for(int i=;i<N-;i++){ //找出停留时间最长的车牌和时间 
        if(strcmp(rec[i].id,rec[i+].id)) temp_time=;  //一个车牌号的查询已经完成，停留总时间归零用于下辆车停留总时间的计算 
        else if(rec[i].status==&&rec[i+].status==){  //有效记录对 
            temp_time+=rec[i+].s-rec[i].s;  //计算某辆车牌号的总时间 
            ++intime[rec[i].s]; //该时刻进的车辆数+1 
            ++outtime[rec[i+].s]; //该时刻出的车辆数+1 

            if(temp_time>max_time){
                max_time=temp_time;num=;//num=0相当于擦除之前的车牌记录，重新记录停留时间更长的车牌 
                strcpy(max_id[num++],rec[i+].id); //记录车牌，同时num++ 
            }else if(temp_time==max_time){
            strcpy(max_id[num++],rec[i+].id);//最长停留时间的车牌可能有大于1种 
            }   
        }
    }
    //查询
    int a,b,c;int qtime;int j=;int ans=; //j表示时间秒；ans表示要输出的答案(answer)，即停留在学校的车辆数 
    for(int i=;i<K;i++){
        scanf("%d:%d:%d",&a,&b,&c);
        qtime=a*+b*+c; //查询时间，单位second 
        while(j<=qtime){
            ans+=intime[j]-outtime[j];
            ++j; //由于时间升序，所以将ans,j都设置在循环外面； 
        }
        printf("%d\n",ans);
    }
    for(int i=;i<num;i++) printf("%s ",max_id[i]); //输出最长停留时间的车牌号 
    printf("%02d:%02d:%02d\n",max_time/,max_time%/,max_time%); //输出对应的时间，注意%02d的格式 
}