1095. Cars on Campus (30) 注意题目所给的信息，k个queries是按时间降序给出的，所以我们遍历时只要对所有记录按照时间排序，再进行遍历即可；否则容易超时 注意in和out的配对，本代码用islegal来核对该条记录是否正确； 对于最大值对应车牌号的储存，用string来记录所有满足条件的车牌号比较方便； 注意最后时间格式的输出；
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node { char plate[12]; int time; int status; bool islegal; }v[10008]; bool sortbyplate(const node &a,const node &b) { if(strcmp(a.plate,b.plate)==0) return a.time<b.time; return strcmp(a.plate,b.plate)<0; } bool sortbytime(const node &a,const node &b) { if(a.islegal==b.islegal) return a.time<b.time; return a.islegal>b.islegal; } void CheckIslegal(struct node v[],int n) { for(int i=0;i<n;++i) { if(i==n-1){ v[i].islegal=false;break; } if(strcmp(v[i].plate,v[i+1].plate)==0) { if(v[i].status&&!v[i+1].status){ v[i].islegal=true; v[i+1].islegal=true;i++; } else v[i].islegal=false; } else v[i].islegal=false; } } int CalMaxtime(struct node v[],int n,string &ans) { int max=-1; for(int i=0;i<n;i++) { if(v[i].islegal&&v[i].status) { int ct=0,j=i; while(j<n&&strcmp(v[i].plate,v[j].plate)==0) { if(v[j].islegal&&v[j].status){ ct+=v[j+1].time-v[j].time; ++j; } ++j; } if(max<ct) { ans.clear(); ans=v[i].plate; max=ct; } else if(max==ct) { ans+=" "; ans+=v[i].plate; } i=j-1; } } return max; } void ReadQuery(struct node v[],int n,int k) { int hh,mm,ss,cur,i=0,cnt=0; while(k--) { scanf("%d:%d:%d",&hh,&mm,&ss); cur=hh*3600+mm*60+ss; while(i<n&&v[i].time<=cur&&v[i].islegal) { if(v[i].status) ++cnt; else --cnt; ++i; } printf("%d\n",cnt); } } int main() { int n,k; int hh,mm,ss; char s[8]; scanf("%d %d",&n,&k); for(int i=0;i<n;++i) { scanf("%s %d:%d:%d %s",v[i].plate,&hh,&mm,&ss,s); v[i].time=hh*3600+mm*60+ss; v[i].status=(s[0]=='i')?1:0; } sort(v,v+n,sortbyplate); CheckIslegal(v,n); string ans=""; int max=CalMaxtime(v,n,ans); sort(v,v+n,sortbytime); ReadQuery(v,n,k); printf("%s d:d:d",ans.c_str(),max/3600,max%3600/60,max%60); return 0; }