CCF-201709-2

我们先来看一下题目

解题思路

你不要看着题目这样，好像要考虑很多东西，优先队列就是干这个的，给个排序规则自动排序，而这个题我们要对时间排序，先来后到，然后还取，先还都取，同时还，小号先还。
优先队列，冲!

代码

#include<iostream>
#include<queue>
using namespace std;
struct node{
    char op;
    int time;
    int num;
    bool operator <(const node a)const{
      if(a.time!=time) return a.time<time;
      else if(a.op!=op) return a.op>op;
      else return a.num<num;
    }
};
const int maxn=1000;
int ans[maxn+1];
int main(){
    priority_queue<node> q;
    node t;
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=n;i++){
      ans[i]=i;
    }
    while(k--){
      int w,s,c;
      cin>>w>>s>>c;
      t.op='G';
      t.num=w;
      t.time=s;
      q.push(t);
      t.op='R';
      t.time=s+c;
      q.push(t);
    }
    while(!q.empty()){
      t=q.top();
      q.pop();
      if(t.op=='G'){
          for(int i=1;i<=n;i++){
            if(ans[i]==t.num) {
                ans[i]=0;break;
            }
          }
      }else{
          for(int i=1;i<=n;i++){
            if(ans[i]==0){
                ans[i]=t.num;break;
            }
          }
      }
    }
    for(int i=1;i<=n;i++)
      cout<<ans[i]<<" ";
    return 0;
}