10020 - Minimal coverage
[cpp]描述：问题就是刘汝佳书上的的区间选择问题，如果不会的话就看看书吧
#include <cstdio>
#include <cstdlib>
#include <cstring>
int n,m;
int cmp(const void *p1,const void *p2)
{
int a=((int *)p1)[0],b=((int *)p1)[1],c=((int *)p2)[0],d=((int *)p2)[1];
if(a<0) a=0;
if(b>m) b=m;
if(c<0) c=0;
if(d>m) d=m;
if( a < c ) return 0;
else if( a == c )
{
if( b < d ) return 0;
else return 1;
}
else return 1;
}
int num[100010][2],score[100010];
int main()
{
//freopen("a.txt","r",stdin);
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
int count=0,sum=0,flag=0,v=0;
while(scanf("%d %d",&num[count][0],&num[count][1])!=EOF)
if(!num[count][0]&&!num[count][1]) break;
else count++;
qsort(num,count,sizeof(num[0]),cmp);
for(int i=0; i<count; i++)
{
if(num[i][0]<=flag&&num[i][1]>flag)
{
if(v<num[i][1])
{
v=num[i][1];
score[sum]=i;
if(v>=m)
{
sum++;
break;
}
}
}
else
{
if(num[i][0]>flag&&num[i][0]<=v&&num[i][1]>v)
{
flag=v;
score[++sum]=i;
v=num[i][1];
if(v>=m)
{
sum++;
break;
}
}
}
}
if(v<m) sum=0;
printf("%d\n",sum);
for(int i=0; i<sum; i++)
printf("%d %d\n",num[score[i]][0],num[score[i]][1]);
if(n) printf("\n");
}
return 0;
}
补充：软件开发 , Java ,
