46525

csp 201709-2 优先队列模拟

数据规模:

  

用优先队列对各个事件的发生先后记录即可:

#include<iostream> #include<queue> using namespace std; int key[1001]; struct node { int no; int begin; int end; int type;//表示借,1表示时在还 node(int no, int begin,int end, int type):no(no),begin(begin),end(end),type(type) { } friend bool operator <(node a, node b) { if(!a.type) { if(!b.type)//都是借 { return a.begin>b.begin; } else//借遇到还的 { return (a.begin>=(b.begin+b.end)); } } else { if (!b.type) { return (a.begin+a.end)>b.begin; } else { //都是还 if((a.begin+a.end)>(b.begin+b.end)) return true; else if((a.begin+a.end)==(b.begin+b.end)) return a.no > b.no; else return false; } } }; }; priority_queue<node> q; int main() { ios::sync_with_stdio(false); int N,k; cin>>N>>k; node t(1,1,1,1); int a,b,c; for(int i=0;i<N;i++) { key[i]=i+1; } while(k--) { cin>>a>>b>>c; q.push(node(a,b,c,0)); q.push(node(a,b,c,1)); } while(!q.empty()) { t=q.top(); //cout<<t.no<<t.type<<endl; if(!t.type) { for (int i = 0; i < N; i++) { if(key[i]==t.no) { key[i]=-1; break; } } } else { for (int i = 0; i < N; i++) { if(key[i]==-1) { key[i]=t.no; break; } } } q.pop(); } for (int i = 0; i < N; i++) { cout<<key[i]<<" "; } return 0; }

来源:博客园

作者:_封刀看海

链接:https://www.cnblogs.com/Crossea/p/11426140.html

Recommend