Distributing Parts

Distributing Parts

题目链接：http://codeforces.com/problemset/problem/496/E

贪心

将音乐和人都以低音升序排序，贪心处理低音更低的音乐，找出低音小于等于它的歌手，二分查找高音与它最近的人。因为剩下的人的低音一定小于后面的歌的低音，而我们选择出了满足条件的高音的最小的人，让后面的歌尽有可能的有人唱。然而不知道为什么我用lower_bound(s.begin(),s.end(),modle)会TLE，而用s.lower_bound(modle)就能过，这两者实现不同吗？

代码如下：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<set>

 #define N 100005

 using namespace std;

 struct nod{

     int l,r,num,index;

 }musics[N],men[N];

 int k[N],ans[N];

 bool cmp(nod a,nod b){

     if(a.l==b.l)return a.r<b.r;

     return a.l<b.l;

 }

 int n,m;

 int main(void){

     scanf("%d",&n);

     for(int i=;i<=n;++i){

         musics[i].num=i;

         scanf("%d%d",&musics[i].l,&musics[i].r);

     }

     sort(musics+,musics++n,cmp);

     scanf("%d",&m);

     for(int i=;i<=m;++i){

         men[i].num=i;

         scanf("%d%d%d",&men[i].l,&men[i].r,&k[i]);

     }

     sort(men+,men++m,cmp);

     bool flag=;

     int tt=;

     set<pair<int,int> >s;

     for(int i=;i<=n;++i){

         while(tt<=m&&men[tt].l<=musics[i].l){

             s.insert(make_pair(men[tt].r,men[tt].num));

             tt++;

         }

         set<pair<int,int> >::iterator it;

         it=s.lower_bound(make_pair(musics[i].r,));

         if(it==s.end()){

             flag=;

             break;

         }

         if(musics[i].r<=it->first){

             ans[musics[i].num]=it->second;

             k[it->second]--;

             if(k[it->second]==)

                 s.erase(*it);

         }else{

             flag=;

             break;

         }

     }

     if(flag){

         printf("YES\n");

         for(int i=;i<=n;++i)

             printf("%d%c",ans[i],n==i?'\n':' ');

     }else printf("NO\n");

 }