题目链接：https://cn.vjudge.net/problem/UVA-11776
题意：
给出数字n（0<=n<=1000），代表有n个农民，接下来有n行，每行两个数字S和E代表这个农民工作时间为[S,E]；
每个农民工作时，需要有一个enforcer来监督，且每个enforcer一次只能监督一个农民；
求最少需要多少个enforcer.
题解：
这道题我也不太清楚算贪心还是算模拟，可能两者都有一点吧。
首先我们根据正常思维，既然要模拟分配监工去监督农民，那么肯定先给第一个开始做的农民分配一个监工；
所以我们自然而然的想到对农民按工作时间的起点S从小到大排序；
然后，我们也就会进一步自然的想到，如果下一个农民的工作时间和当前农民的工作时间有重合，就要再来一个监工；
但是，经过更加仔细的思考，
由于我们是按农民工作时间的起点S从小到大排，而非按工作终点E排，故可能出现问题：
3
1 5
2 3
4 10
这种情况，如果单纯地像上面说的那样算，就会算出需要3个监工，而事实上，只需要2个监工就够了。
所以，我们建立一个优先队列，用以存储表示每个监工的监督时间；
并且每个监工有两个变量l和r，表示在当前，监工的工作时间为[l,r]，而优先队列按监督时间的终点从小到大维护。
这样一来，我们就有更加成熟的思路：
①把第一个的农民的工作时间[S,E]当做第一个监工的监督时间[l,r]存入优先队列。
②枚举之后的农民；
③获得队头的值（代表了当前所有监工中，最早空下来的那个），与当前农民进行比较：
若当前监工还未空闲，说明所有监工都没空，只能在加一个监工；
若当前监工已经空闲，可以监督当前农民，则取出队头，[l,r]修改成当前农民的[S,E]值，再push入优先队列；
④所有农民枚举完毕，ans = 优先队列的size；
AC代码：
1 #include
2 #include
3 #include
4 using namespace std;
5 struct Node{
6 int l,r;
7 bool operator<(const Node &oth)const
8 {
9 return this->r > oth.r;
10 }
11 }node[1000+5];
12 int n;
13 bool cmp(Node a,Node b){return a.l<b.l;}
14 int main()
15 {
16 int kase=0;
17 while(scanf("%d",&n) && n!=-1)
18 {
19 if(n==0)
20 {
21 printf("Case %d: 0\n",++kase);
22 continue;
23 }
24
25 priority_queue enforcer;
26 for(int i=0;i"%d%d",&node[i].l,&node[i].r);
27 sort(node,node+n,cmp);
28 enforcer.push(node[0]);
29 for(int i=1;i)
30 {
31 Node now=enforcer.top();
32 if(node[i].l<=now.r) enforcer.push(node[i]);
33 else
34 {
35 enforcer.pop();
36 now.l=node[i].l, now.r=node[i].r;
37 enforcer.push(now);
38 }
39 }
40
41 printf("Case %d: %d\n",++kase,enforcer.size());
42 }
43 }
UVA 11776 - Oh Your Royal Greediness! - [贪心/模拟]
京公网安备 11010802041100号