poj 3614 Sunscreen (贪心)

题目链接: poj 3614

题目大意: 给出N个区间，然后M个数，每个数最多可以匹配Ki次

问最多有多少个区间能被匹配

解题思路: 若按区间起点从小到大开始排，每个数按从小到大开始排

下面这种情况会过不了

1 9 6

2 6 9

既会出现k2可以同时匹配X1和X2，但k2只能匹配X1，若选择k1匹配x1则结果是错误的

这种情况只有在X1区间包含X2区间的时候才会出现，所以避免这种情况可以按区间终点排序

代码:< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">#include #include #include #include using namespace std; #define MAX 2600 struct snode{ int x,y; }Num1[MAX],Num2[MAX]; bool cmp(struct snode a,struct snode b) { return a.y =1&&Num2[j].x>=Num1[i].x&&Num2[j].x<=Num1[i].y) //找到第一个符合条件 { sum++; Num2[j].y--; break; } else if(Num2[j].x>Num1[i].y) //若bottle的SPF比cow的MaxSPF还大则退出循环 break; //剪枝 } } printf("%d\n",sum); } return 0; }