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;
}