本文主要是介绍Codeforces Round #283 (Div. 2) E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
E. Distributing Parts
题意：一个节目，有n个部分，每部分有一个范围；有m个人，每个人有个能力范围，能表演若干部分。如果人的范围包含了某个部分的范围，就能表演那个部分，问如何分配。
思路：贪心+平衡二叉树(set)上查找。将每个部分和人按范围的下界排序，然后对每个部分，把下界满足表演要求的人加到集合里去维护，然后贪心找一个上界尽量小的人去表演这一部分。
注意在集合中查找时，不要用std::lower_bound()，它的复杂度是O(n)。。。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <memory.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;const int maxn=100010;struct Part{int a,b;int id;bool operator<(const Part& q)const{return a<q.a;}
}part[maxn];struct Actor{int c,d;int id;bool operator<(const Actor& q)const{return c<q.c;}
}actor[maxn];struct Node{int x;int id;Node(int x,int id):x(x),id(id){ }bool operator<(const Node& q)const{if(x==q.x)return id<q.id;return x<q.x;}
};int cnt[maxn];
int ans[maxn];int main(){int n,m;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&part[i].a,&part[i].b);part[i].id=i+1;}scanf("%d",&m);for(int i=0;i<m;i++){scanf("%d%d%d",&actor[i].c,&actor[i].d,&cnt[i]);actor[i].id=i+1;}sort(part,part+n);sort(actor,actor+m);bool ok=1;int k=0;set<Node> Set;set<Node>::iterator it;for(int i=0;i<n;i++){ //枚举每个部分 for(;k<m;k++){if(part[i].a>=actor[k].c){Set.insert(Node(actor[k].d,actor[k].id)); //对当前部分，把下界满足的演员加到集合里去维护 }else{break;}}it=Set.lower_bound(Node(part[i].b,0)); //贪心找上界尽量小的演员去表演该部分 if(it!=Set.end()){ans[part[i].id]=(*it).id;if(--cnt[(*it).id-1]==0){Set.erase(it);}}else{ok=0;break;}}if(ok){printf("YES\n");for(int i=1;i<=n;i++){printf("%d ",ans[i]);}printf("\n");}else{printf("NO\n");}return 0;
}这篇关于Codeforces Round #283 (Div. 2) E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
