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