PAT甲级(Advanced Level) Cars on Campus (30)

怼烎@ 2023-06-30 09:21 39阅读 0赞

思路：

（1）将vector先按plate\_number排序，若相同则按时间大小排序，这样可以使一个plate\_number的记录按时间顺序排在一起

（2） 遍历vector，若前一条数据的plate\_number与后一条相同，且前一条是in后一条是out，则为合法数据

我设了一个数组cars,cars\[i\]表示第i秒，停车场内的车数

那么对于一对合法数据，我们可以求得intime和outtime（以秒为单位），然后在这个范围内循环使cars\[i\]++即可

同时可以用map<string,int>记录每个车的停车时间。

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <stdio.h>
    using namespace std;
    int n,k,maxparttime=-1;
    struct Record{
        string plate_number;
        string time;
        int h,m,s,flag;//0-in  1-out
        Record(){}
        Record(string plate_number,string time,string status){
            this->plate_number = plate_number;
            this->time = time;
            sscanf(time.c_str(),"%d:%d:%d",&h,&m,&s);
            (status == "in") ? flag = 0 : flag = 1;
        }
    };
    vector<Record> v;
    map<string,int> parttime;
    int cars[3600*24]={0};
    bool cmp(Record r1,Record r2){
        if(r1.plate_number != r2.plate_number){
            return r1.plate_number < r2.plate_number;
        }
        return r1.time<r2.time;
    }
    int main()
    {
        cin>>n>>k;
        string plate,time,status;
        for(int i=0;i<n;i++){
            cin>>plate>>time>>status;
            v.push_back(Record(plate,time,status));
        }
        sort(v.begin(),v.end(),cmp);
        for(int i=1;i<v.size();i++){
            if(v[i].plate_number == v[i-1].plate_number && v[i-1].flag == 0 && v[i].flag == 1){
                int intime = v[i-1].h * 3600 + v[i-1].m*60 + v[i-1].s;
                int outtime = v[i].h * 3600 + v[i].m*60 + v[i].s;
                for(int i=intime;i<outtime;i++){
                    cars[i]++;
                }
                parttime[v[i].plate_number] += 3600*(v[i].h-v[i-1].h) + 60*(v[i].m-v[i-1].m) + (v[i].s - v[i-1].s);
                if(parttime[v[i].plate_number] > maxparttime){
                    maxparttime = parttime[v[i].plate_number];
                }
            }
        }
        string query;
        int h,m,s;
        for(int i=0;i<k;i++){
            cin>>query;
            sscanf(query.c_str(),"%02d:%02d:%02d",&h,&m,&s);
            cout<<cars[h*3600+m*60+s]<<endl;
        }
        for(auto it=parttime.begin();it!=parttime.end();it++){
            if(it->second == maxparttime){
                cout<<it->first<<" ";
            }
        }
        printf("%02d:%02d:%02d\n",maxparttime/3600,maxparttime%3600/60,maxparttime%3600%60);
        return 0;
    }