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.Bkjia.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; }