PAT甲题题解-1095. Cars on Campus(30)-（map+树状数组，或者模拟）

题意：给出n个车辆进出校园的记录，以及k个时间点，让你回答每个时间点校园内的车辆数，最后输出在校园内停留的总时间最长的车牌号和停留时间，如果不止一个，车牌号按字典序输出。

几个注意点：

1.如果一个车连续多次进入，只取最后一个

2.如果一个车连续多次出去，只取第一个

3.一个车可能出入校园内好几次，停留时间取总和

实际上题目就是让我们求某个时间段内的车辆总和，时间段其实就相当于一个区间，区间求和的话，很快就联想到树状数组和线段树。然而怎么将时间段和区间联系起来呢，那就存储出现在记录和询问里的所有时间点，从小到大排序，索引即为区间中节点的编号。

那么问题就转化为车辆停留的时间对应区间[l,r]，该区间内每个时间点的车辆数都+1，询问就是求某个点的值。这里就采用了树状数组的“区间更新，单点查询”，不理解的可以参考下面链接：

http://www.cnblogs.com/chenxiwenruo/p/3430920.html

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

#include <map>

/*

有时候第五个样例会超时，限时220ms，运行的话208ms。

*/

using namespace std;

const int maxn=+;

string timeline[maxn];  //存储出现的时间

string query[maxn];

int parking[maxn]; //树状数组，用于统计区间内的车辆数

int timecnt=;

map<string,int>visnumber; //记录出现的车牌号

map<string,int>vistime; //记录出现的每个时间点

struct Record{

    string plate_number;

    string time;

    char status[];

    bool operator<(const Record tmp)const{

        //不知道为啥，原本<=0就会导致在第3、6个样例段中对record的sort排序产生段错误

        if(time.compare(tmp.time)<)

            return true;

        else

            return false;

    }

}record[maxn];

struct Car{

    string plate_number;

    //char time[10];

    int l,r;

    int timelength=;

    bool operator<(const Car tmp)const{

        if(timelength==tmp.timelength){

            if(plate_number.compare(tmp.plate_number)<=)

                return true;

            else

                return false;

        }

        else

            return timelength>tmp.timelength;

    }

}car[maxn];

/*

二分查找某个时间点对应的索引

*/

int binarySearch(string str){

    int l=,r=timecnt,mid;

    while(r>=l){

        mid=(l+r)>>;

        if(str.compare(timeline[mid])==)

            return mid;

        if(str.compare(timeline[mid])<){

            r=mid-;

        }

        else{

            l=mid+;

        }

    }

    return -;

}

//以下三个函数为树状数组的操作

int lowbit(int x){

    return x&(-x);

}

/*

区间更新

*/

void update(int x,int val){

    while(x){

        parking[x]+=val;

        x-=lowbit(x);

    }

}

/*

单点求和

*/

int sum(int x){

    int sum=;

    while(x<maxn){

        sum+=parking[x];

        x+=lowbit(x);

    }

    return sum;

}

int main()

{

    int n,k;

    scanf("%d %d",&n,&k);

    for(int i=;i<=n;i++){

        cin>>record[i].plate_number>>record[i].time;

        scanf("%s",record[i].status);

    }

    sort(record+,record+n+);

    timecnt=;

    timeline[++timecnt]="00:00:00";

    vistime["00:00:00"]=;

    timeline[++timecnt]="23:59:59";

    vistime["23:59:59"]=;

    for(int i=;i<=n;i++){

        if(!vistime[record[i].time]){

            vistime[record[i].time]=;

            timeline[++timecnt]=record[i].time;

        }

    }

    for(int i=;i<k;i++){

        cin>>query[i];

        if(!vistime[query[i]]){

            timeline[++timecnt]=query[i];

            vistime[query[i]]=;

        }

    }

    sort(timeline+,timeline+timecnt+);

    int carcnt=;

    /*

    求每辆车进出校园对应的时间区间段，以及停留的时间

    同一辆车连续多次进入，取最后一个。

    同一辆车连续多次出去，取第一个。

    */

    for(int i=;i<=n;i++){

        if(record[i].status[]=='i'){

            visnumber[record[i].plate_number]=i;

        }

        else if(visnumber[record[i].plate_number]!= && record[i].status[]=='o'){

            int in=visnumber[record[i].plate_number];

            car[carcnt].plate_number=record[i].plate_number;

            car[carcnt].l=binarySearch(record[in].time);

            car[carcnt].r=binarySearch(record[i].time);

            int hh1,mm1,ss1;

            int hh2,mm2,ss2;

            hh2=(record[i].time[]-'')*+(record[i].time[]-'');

            mm2=(record[i].time[]-'')*+(record[i].time[]-'');

            ss2=(record[i].time[]-'')*+(record[i].time[]-'');

            hh1=(record[in].time[]-'')*+(record[in].time[]-'');

            mm1=(record[in].time[]-'')*+(record[in].time[]-'');

            ss1=(record[in].time[]-'')*+(record[in].time[]-'');

            car[carcnt].timelength=(hh2*+mm2*+ss2)-(hh1*+mm1*+ss1);

            visnumber[record[i].plate_number]=; //这样做是可能后来该车又进来

            carcnt++;

        }

    }

    memset(parking,,sizeof(parking));

    /*

    如果某辆车l进、r出，则对应区间段[l,r-1]的车辆数+1

    */

    for(int i=;i<carcnt;i++){

        int l=car[i].l;

        int r=car[i].r;

        //更新[l,r-1)，该区间内每个时间段数量都+1。相当于[1,r-1]的先+1，[1,l-1]的再-1

        update(r-,);

        update(l-,-);

    }

    //求对应某个时间点，校园的车辆数

    for(int i=;i<k;i++){

        int idx=binarySearch(query[i]);

        printf("%d\n",sum(idx));

    }

    visnumber.clear();

    //有可能一辆车进出校园好几次，所以要将停留的时间累加

    for(int i=;i<carcnt;i++){

        if(!visnumber[car[i].plate_number]){

            visnumber[car[i].plate_number]=i;

        }

        else{

            int idx=visnumber[car[i].plate_number];

            car[idx].timelength+=car[i].timelength;

        }

    }

    sort(car,car+carcnt);

    cout<<car[].plate_number;

    for(int i=;i<carcnt;i++){

        if(car[i].timelength==car[].timelength){

            cout<<" "<<car[i].plate_number;

        }

    }

    int h=car[].timelength/;

    int m=(car[].timelength%)/;

    int s=car[].timelength%;

    printf(" %02d:%02d:%02d\n",h,m,s);

    return ;

}

（其实这题也可以纯按模拟题来做，用树状数组有点大材小用了，按照记录的时间排序，模拟车辆的进出，用一个变量记录校园当前的车辆数量。）

巴特西

PAT甲题题解-1095. Cars on Campus(30)-（map+树状数组，或者模拟）

最新文章

热门文章