首页 > 代码库 > Codeforces_496_E

Codeforces_496_E

http://codeforces.com/problemset/problem/496/E

 

这好像叫序列混合贪心,简单地讲,用歌去匹配最符合条件的人。用了multiset,重载了<,加快寻找最符合条件的人的速度。

 

#include<cstdio>#include<iostream>#include<algorithm>#include<set>using namespace std;struct song{public:    int low,high,flag,num;    friend bool operator<(const song x,const song y)    {        return x.high < y.high;    }}a[200010];int ans[100005],counts[100005];bool cmp(song x,song y){    if(x.low != y.low)  return x.low < y.low;    return x.flag < y.flag;}int main(){    multiset<song> s;    multiset<song>::iterator it;    int n,m;    cin >> n;    for(int i = 1;i <= n;i++)    {        cin >> a[i].low >> a[i].high;        a[i].flag = 1;        a[i].num = i;    }    cin >> m;    for(int i = n+1;i <= m+n;i++)    {        cin >> a[i].low >> a[i].high >> counts[i-n];        a[i].flag = 0;        a[i].num = i-n;    }    sort(a+1,a+1+m+n,cmp);    s.clear();    for(int i = 1;i <= m+n;i++)    {        if(a[i].flag)        {            it = s.lower_bound(a[i]);            if(it == s.end())            {                cout << "NO" << endl;                return 0;            }            else            {                ans[a[i].num] = it->num;                counts[it->num]--;                if(!counts[it->num])                {                    s.erase(it);                }            }        }        else        {            s.insert(a[i]);        }    }    cout << "YES" << endl;    int i;    for(i = 1;i < n;i++)    {        cout << ans[i] << " ";    }    cout << ans[i] << endl;    return 0;}

 

Codeforces_496_E