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的格式 
}