用priority_queue的一个典型例题，记录一下。
#include<iostream> #include<map> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<math.h> using namespace std; struct people{ int arrive; int start; int process; bool operator<(const people& p) const{ return arrive>p.arrive; } }; struct cmp1{ bool operator() (people a,people b){ return (a.start+a.process)>(b.start+b.process); } }; priority_queue<people,vector<people>,cmp1> bank; priority_queue<people> wait; int parseStr(string str){ int h=stoi(str.substr(0,2)); //cout<<"h:"<<h<<endl; int m=stoi(str.substr(3,2)); //cout<<"m:"<<m<<endl; int s=stoi(str.substr(6,2)); //cout<<"s:"<<s<<endl; //cout<<"parse:"<<h*60*60+m*60+s<<endl; return h*60*60+m*60+s; } int main(){ int num; int bcnt; cin>>num>>bcnt; int realnum=num; for(int i=0;i<num;i++){ string arrive; int process; cin>>arrive>>process; if(arrive<="17:00:00"){ int arr=parseStr(arrive); people* p=new people(); p->arrive=arr; p->process=process*60; wait.push(*p); //cout<<"$$$:"<<wait.top().arrive<<endl; }else{ realnum--; } } int curtime=8*3600; int totalwait=0; int curcnt=0; //cout<<curtime<<endl; while(!wait.empty()){ //cout<<"!!!:"<<curtime<<endl; if(!bank.empty()){ people btop=bank.top(); people wtop=wait.top(); if((btop.start+btop.process)<wtop.arrive){ bank.pop(); curtime=btop.start+btop.process; totalwait+=btop.start-btop.arrive; curcnt--; }else if(curcnt<bcnt){ wait.pop(); curtime=max(curtime,wtop.arrive); wtop.start=curtime; bank.push(wtop); curcnt++; }else{ bank.pop(); curtime=btop.start+btop.process; totalwait+=btop.start-btop.arrive; wait.pop(); wtop.start=curtime; bank.push(wtop); } }else{ people wtop=wait.top(); wait.pop(); curtime=max(curtime,wtop.arrive); //cout<<"???:"<<curtime<<endl; wtop.start=curtime; bank.push(wtop); curcnt++; } //cout<<curtime<<endl; } while(!bank.empty()){ people out=bank.top(); bank.pop(); totalwait+=out.start-out.arrive; } //cout<<totalwait<<endl; double res=((double)totalwait)/60/realnum; printf("%.1f",res); return 0; }
