本文主要是介绍uva 10020 Minimal coverage(贪心，区间覆盖)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题一读就是经典的区间问题，是区间覆盖，敲过之后还有花了很长的调试时间，还是我不熟练，现在做题确实挺慢
的，简单题目也要做好久，没事，慢慢来。最重要的要确保正确率和心态问题，认真对待，调试找到了好多bug，一些
细节问题。。。都是刚开始没有注意到的。交了之后RE，在数组上多加了两个0。A了，，uva老是不提示数据有多大，
所以只能乱开。。。
思路：
先对区间按左边的点进行排序，如果当前需要涵盖的区间为[x，y]，那么在排序的区间中到左边小于x，右
边最大的那个区间，设为Max，然后更新想找的区间为[Max，m]，依次类推，知道没有小于x的区间或者最大值已经大
于了m。。
贴代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node
{int x,y;
}a[500005],b[500005];
int cmp(const void *a,const void *b)
{if(((node *)a)->x == ((node *)b)->x)return ((node *)b)->y - ((node *)b)->y;return ((node *)a)->x - ((node *)b)->x;
}
int main()
{int T,i,m,x,y;cin >> T;while(T--){cin >> m;i = 1;while(cin >> x >> y,x||y){a[i].x = x;a[i].y = y;i++;}int s = i-1; qsort(a+1,s,sizeof(a[0]),cmp);// for(i=1; i<=s; i++)// cout << a[i].x << " " << a[i].y << endl;int cnt = 0;int flag = 0;int k=1;int flag1 = 0;int Max = 0;int Max1;for(i=1; i<=s; i++){if(a[i].x <= cnt){if(Max <= a[i].y){Max = a[i].y;Max1 = a[i].x; }flag = 1;if(i!=s)continue;} if(i != s)i--;// cout << " i= " << i << endl;if(flag == 0){break;}b[k].x = Max1;b[k].y = Max;//cout << a[i].x << a[i].y << endl;k++;cnt = Max;flag = 0;if(cnt >= m){flag1 = 1;break;}}if(flag1){cout << k-1 << endl;for(i=1; i<k; i++){cout << b[i].x << " " << b[i].y <<endl; }}else {cout << '0' << endl;}if(T)cout << endl;} return 0;
}
这篇关于uva 10020 Minimal coverage(贪心，区间覆盖)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
