Minimal coverage -uva 覆盖线段，贪心

本文主要是介绍Minimal coverage -uva 覆盖线段，贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道经典的贪心问题，具体方法就是将（an,bn)区间，按照an从小到大的顺序进行排序，之后从0开始，

取最大的有效区间，这里用到了结构体的快排，否则可能会超时.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 100000 + 10
#define BOTTOM -50000 - 10
struct Points
{int x,y;
}a[MAX_SIZE],b[MAX_SIZE];
int cmp(const void *a,const void *b)
{struct Points * c=(Points*)a;struct Points * d=(Points*)b;if(c->x!=d->x)return c->x - d->x;/*升序*/elsereturn c->y - d->y;
}
int main()
{int M,N,m,n,i,j,cases,t,p,q,min,max;scanf("%d",&N);for(cases=1;cases<=N;cases++){int ok=0,k;scanf("%d",&M);for(i=0,j=0;scanf("%d%d",&m,&n);){if(!m&&!n) break;if(m<M&&n>0) /*不在范围内的直接舍去*/{a[j].x=m;a[j].y=n;j++;}}qsort(a,j,sizeof(a[0]),cmp);if(a[0].x>0||j==0) {printf("0\n");continue;}for(i=0,t=0,q=0,max=BOTTOM;i<j;i++){if(a[i].x<=t){m=a[i].y-t;/*有效长度*/if(m>max){max=m;p=i;/*储存坐标*/}}if(a[i+1].x>t||i==j-1)/*如果下一个坐标大于*/{/*就对上面所计算的区间进行取长*/b[q].x=a[p].x;b[q].y=a[p].y;q++;t=a[p].y;max=BOTTOM;}if(t>=M) break;}if(t>=M) ok=1;/*for(i=0;i<q;i++)printf("%d %d\n",b[i].x,b[i].y);*/if(ok){printf("%d\n",q);for(i=0;i<q;i++)printf("%d %d\n",b[i].x,b[i].y);}elseprintf("0\n");if(cases<N)printf("\n");memset(a,0,sizeof(a));memset(b,0,sizeof(b));}return 0;
}

这篇关于Minimal coverage -uva 覆盖线段，贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---