题意：给出n个车辆进出校园的记录，以及k个时间点，让你回答每个时间点校园内的车辆数，最后输出在校园内停留的总时间最长的车牌号和停留时间，如果不止一个，车牌号按字典序输出。
几个注意点：
1.如果一个车连续多次进入，只取最后一个
2.如果一个车连续多次出去，只取第一个
3.一个车可能出入校园内好几次，停留时间取总和
实际上题目就是让我们求某个时间段内的车辆总和，时间段其实就相当于一个区间，区间求和的话，很快就联想到树状数组和线段树。然而怎么将时间段和区间联系起来呢，那就存储出现在记录和询问里的所有时间点，从小到大排序，索引即为区间中节点的编号。
那么问题就转化为车辆停留的时间对应区间[l,r]，该区间内每个时间点的车辆数都+1，询问就是求某个点的值。这里就采用了树状数组的“区间更新，单点查询”，不理解的可以参考下面链接：
http://www.cnblogs.com/chenxiwenruo/p/3430920.html
#include #include #include #include <string.h> #include <string> #include /* 有时候第五个样例会超时，限时220ms，运行的话208ms。 */ using namespace std; const int maxn=90000+5; string timeline[maxn]; //存储出现的时间 string query[maxn]; int parking[maxn]; //树状数组，用于统计区间内的车辆数 int timecnt=0; map<string,int>visnumber; //记录出现的车牌号 map<string,int>vistime; //记录出现的每个时间点 struct Record{ string plate_number; string time; char status[5]; bool operator<(const Record tmp)const{ //不知道为啥，原本<=0就会导致在第3、6个样例段中对record的sort排序产生段错误 if(time.compare(tmp.time)<0) return true; else return false; } }record[maxn]; struct Car{ string plate_number; //char time[10]; int l,r; int timelength=0; bool operator<(const Car tmp)const{ if(timelength==tmp.timelength){ if(plate_number.compare(tmp.plate_number)<=0) return true; else return false; } else return timelength>tmp.timelength; } }car[maxn]; /* 二分查找某个时间点对应的索引 */ int binarySearch(string str){ int l=1,r=timecnt,mid; while(r>=l){ mid=(l+r)>>1; if(str.compare(timeline[mid])==0) return mid; if(str.compare(timeline[mid])<0){ r=mid-1; } else{ l=mid+1; } } return -1; } //以下三个函数为树状数组的操作 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=0; while(x<maxn){ sum+=parking[x]; x+=lowbit(x); } return sum; } int main() { int n,k; scanf("%d %d",&n,&k); for(int i=1;i<=n;i++){ cin>>record[i].plate_number>>record[i].time; scanf("%s",record[i].status); } sort(record+1,record+n+1); timecnt=0; timeline[++timecnt]="00:00:00"; vistime["00:00:00"]=1; timeline[++timecnt]="23:59:59"; vistime["23:59:59"]=1; for(int i=1;i<=n;i++){ if(!vistime[record[i].time]){ vistime[record[i].time]=1; timeline[++timecnt]=record[i].time; } } for(int i=0;i){ cin>>query[i]; if(!vistime[query[i]]){ timeline[++timecnt]=query[i]; vistime[query[i]]=1; } } sort(timeline+1,timeline+timecnt+1); int carcnt=0; /* 求每辆车进出校园对应的时间区间段，以及停留的时间 同一辆车连续多次进入，取最后一个。 同一辆车连续多次出去，取第一个。 */ for(int i=1;i<=n;i++){ if(record[i].status[0]=='i'){ visnumber[record[i].plate_number]=i; } else if(visnumber[record[i].plate_number]!=0 && record[i].status[0]=='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[0]-'0')*10+(record[i].time[1]-'0'); mm2=(record[i].time[3]-'0')*10+(record[i].time[4]-'0'); ss2=(record[i].time[6]-'0')*10+(record[i].time[7]-'0'); hh1=(record[in].time[0]-'0')*10+(record[in].time[1]-'0'); mm1=(record[in].time[3]-'0')*10+(record[in].time[4]-'0'); ss1=(record[in].time[6]-'0')*10+(record[in].time[7]-'0'); car[carcnt].timelength=(hh2*3600+mm2*60+ss2)-(hh1*3600+mm1*60+ss1); visnumber[record[i].plate_number]=0; //这样做是可能后来该车又进来 carcnt++; } } memset(parking,0,sizeof(parking)); /* 如果某辆车l进、r出，则对应区间段[l,r-1]的车辆数+1 */ for(int i=0;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-1,1); update(l-1,-1); } //求对应某个时间点，校园的车辆数 for(int i=0;i){ int idx=binarySearch(query[i]); printf("%d\n",sum(idx)); } visnumber.clear(); //有可能一辆车进出校园好几次，所以要将停留的时间累加 for(int i=0;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<0].plate_number; for(int i=1;i){ if(car[i].timelength==car[0].timelength){ cout<<" "<<car[i].plate_number; } } int h=car[0].timelength/3600; int m=(car[0].timelength%3600)/60; int s=car[0].timelength%60; printf(" %02d:%02d:%02d\n",h,m,s); return 0; }
（其实这题也可以纯按模拟题来做，用树状数组有点大材小用了，按照记录的时间排序，模拟车辆的进出，用一个变量记录校园当前的车辆数量。）
京公网安备 11010802041100号