题目链接: poj 3614
题目大意: 给出N个区间,然后M个数,每个数最多可以匹配Ki次
问最多有多少个区间能被匹配
解题思路: 若按区间起点从小到大开始排,每个数按从小到大开始排
下面这种情况会过不了
1 9 6
2 6 9
既会出现k2可以同时匹配X1和X2,但k2只能匹配X1,若选择k1匹配x1则结果是错误的
这种情况只有在X1区间包含X2区间的时候才会出现,所以避免这种情况可以按区间终点排序
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> 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<b.y?true:false; } bool comp(struct snode a,struct snode b) { return a.x<b.x?true:false; } int main() { int i,j,n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { scanf("%d%d",&Num1[i].x,&Num1[i].y); } for(i=1;i<=m;i++) { scanf("%d%d",&Num2[i].x,&Num2[i].y); } sort(Num1+1,Num1+1+n,cmp); //Cow按MaxSPF从小到大排 sort(Num2+1,Num2+1+m,comp); //bottle按从小到大排 int sum=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(Num2[j].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; }