关于算法-数据结构:PAT甲级1095-Cars-on-Campus

题目粗心：

给出N条记录，每条记录给出一辆车的车牌号、以后时刻以及出入校状况(入校(in)还是出校out))。而后给出K个查问，每个查问给出一个时刻，输入在这个时刻校园内的车辆数。查问结束后输入在学校内停留时间最长的车辆的车牌号(如果有多个，就一并输入)和
对应的停留时间。

算法思路：

该题和1016 Phone Bills的数据处理要求很类似， 这里要求给定某一个时刻，要求以后时刻有多少辆车在停车场，最直观的想法就是用一个变量(car_num)来记录车辆数目，从开始时刻到查问时刻，遇到in的记录就加一，遇到out的时候就减一，而后就失去以后查问时刻有多少车辆存在停车场了，然而该应用办法有一个前提条件，那就是所有的记录都得是无效记录，然而这里的记录有可能是有效的，所以，第一件事就是将记录所有的无效记录全副筛选进去寄存在valid_records数组中，而后对于对于每一次查问就能够依照上述办法取得车辆数目，对于最长的停车工夫长度能够在筛选无效记录的时候记录最长的停车工夫和对应的车牌号码。

排序规定1：

首先依照车牌号分组，依照字典序排序，对于车牌号雷同的依照工夫先后排序，这是为了筛选无效记录。

排序规定2：

依照工夫先后排序。 

筛选无效记录的办法：

先依照排序规定一进行排序,应用指针i遍历所有的记录，这里的i最大为N-2,因为无效记录为一对，所以i<N-1即可。首先得判断i和i+1条记录为同一辆车的记录，否则无意义，而后再判断i和i+1的status别离为in和out，这样的记录才是一对无效记录，对于每一条无效记录，咱们将i和i+1增加进valid_records数组中，而后再累计该车辆的停车工夫，这里应用map<string,int> cars进行存储每一辆车对应的累计停车工夫，
最初在记录最大的停车时长即可(用max_parking_time记录)

获取查问时刻停车场的车辆数目的办法：

先依照排序规定2排序，而后咱们留神到查问的时刻是顺次递增的，也就是说，如果每一次查问都是从都开始查问的话，会和上一次查问的记录反复，能够采取紧接着上一次查问地位往后查问车辆进出状况的办法，咱们应用index记录上一次查问的记录地位，初始为0，应用car_num记录上一次查问停车场车辆的停留数目，只有以后index指向的记录的工夫<=查问工夫，那么就反复以下操作：

1、如果index指向记录的status为in,car_num++;
2、如果index指向记录的status为out,car_num--;

留神:

1、对同一辆车来说，配对的on和off必须满足在把这辆车的记录按工夫顺序排列后，在它们之间不容许呈现其余on或者off的记录;否则，将被视为有效记录。
2、如果每一次查问都是从00:00:00开始查问的话，会超时。 
 3、有可能查问工夫在所有记录时刻之后，比方查问为23:59:59，然而记录的最靠后的工夫为20:00:00,那么index得判断是否将valid_records遍历结束了。测试点1和2考查该点(本人测试失去的后果，不肯定精确) 

提交后果：

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector> 
#include<map>

using namespace std;

struct Record{
    string plate_number ;//车牌号码 
    int time;
    bool status;// in为true,out为false 
};

int getSeconds(int hh,int mm,int ss){
    return hh*3600+mm*60+ss;
}

bool cmp(Record a,Record b){
    if(a.plate_number!=b.plate_number){
        return a.plate_number<b.plate_number;
    }else{
        return a.time<b.time;
    }
}

bool cmpByTime(Record a,Record b){
    return a.time<b.time;
}

int main(){
    int N,K;//记录总数和查问总数
    scanf("%d %d",&N,&K);
    vector<Record> records;
    Record record;
    char plate_number[20];
    int hh,mm,ss;
    char status[10];
    for(int i=0;i<N;++i){
        scanf("%s %d:%d:%d %s",plate_number,&hh,&mm,&ss,status);
        record.plate_number = plate_number;
        record.time = getSeconds(hh,mm,ss);
        record.status = strcmp(status,"in")==0;
        records.push_back(record);
    }
    sort(records.begin(),records.end(),cmp);
    //筛选有效记录
    map<string,int> cars;//每一辆车停车的最长工夫 
    int max_parking_time = -1;//最长停车工夫 
    vector<Record> valid_records;
    int begin=0,next=0;
    for(int i=0;i<N-1;++i){
        if(records[i].plate_number==records[i+1].plate_number){
            // i和i+1是同一辆车
            if(records[i].status&&!records[i+1].status){
                //i为in,i+1为out,i与i+1为一对无效记录 
                valid_records.push_back(records[i]);
                valid_records.push_back(records[i+1]);
                int parking_time = records[i+1].time-records[i].time;//停车工夫 
                // 更新该辆车的累计停车工夫
                cars[records[i].plate_number] += parking_time;  
                max_parking_time = max_parking_time<cars[records[i].plate_number]?cars[records[i].plate_number]:max_parking_time;//更新所有车辆最长停车工夫 
            }
        }
    }
    //依据工夫进行排序
    sort(valid_records.begin(),valid_records.end(),cmpByTime);
    //查问开始
    int index = 0;//以后查问记录的下标 
    int car_num = 0;//以后停车场的车辆数目 
    for(int i=0;i<K;++i){
        scanf("%d:%d:%d",&hh,&mm,&ss);
        int query_time = getSeconds(hh,mm,ss);
        // 从index始终找到停车工夫大于query_time的后面一辆记录即可 
        while(index<valid_records.size()&&valid_records[index].time<=query_time){
            if(valid_records[index].status){
                ++car_num;
            }else{
                --car_num;
            }
            ++index;
        }
        printf("%d\n",car_num);
    }
    //输入最长停车工夫的车牌号和工夫
    map<string,int>::iterator it;
    for(it=cars.begin();it!=cars.end();++it){
        if(it->second==max_parking_time){
            printf("%s ",it->first.c_str());
        }
    }
    printf("%02d:%02d:%02d",max_parking_time/3600,max_parking_time%3600/60,max_parking_time%60);
    return 0;
}