本文主要是介绍ural Minimal Coverage (区间覆盖)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.timus.ru/problem.aspx?space=1&num=1303
给出一些区间，选择尽量少的区间能覆盖到[0,m]。
小白p154，典型的区间覆盖问题。一直在想怎么dp。。
首先预处理，先按左端点从小到大排序，若左端点相同右端点从大到小排序，若区间x完全包含y，按照贪心的思想，y是没有意义的，有大区间可以选何必选择小区间。处理完事之后各个区间满足a1 <= a2 <= a3....且b1 <= b2 <= b3...
这样找到第一个覆盖0的区间之后，记录上一个区间所能到达的最右边位置，然后去找一个左端点最接近该位置的区间继续覆盖，直到覆盖到M点。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;struct Line
{int l,r;bool operator < (const struct Line &tmp)const{if(l == tmp.l)return r > tmp.r;return l < tmp.l;}
} b[100010],a[100010],ans[100010];int main()
{int m,t1,t2;while(~scanf("%d",&m)){int l,r;t1 = 0;while(~scanf("%d %d",&l,&r)){if(l == 0 && r == 0)break;a[++t1] = (struct Line){l,r};}sort(a+1,a+1+t1);t2 = 1;b[1] = a[1];for(int i = 2; i <= t1; i++){if(a[i].r < 0 || a[i].l > m)continue;if(!(a[i].l >= b[t2].l && a[i].r <= b[t2].r))//包含的区间去掉b[++t2] = a[i];}t2++;b[t2] = (struct Line){m+1,m+1};int k = 0;int e = -1,i;for(i = 1; i < t2; i++){if(b[i].l <= 0 && b[i+1].l > 0){ans[++k] = b[i];e = b[i].r;break;}}if(k == 0){printf("No solution\n");continue;}for(; i < t2; i++){if(e >= m)break;if(b[i].l <= e && b[i+1].l > e) //找到最接近上一个区间端点的区间覆盖{ans[++k] = b[i];e = b[i].r;}}if(e < m){printf("No solution\n");continue;}else{printf("%d\n",k);for(int i = 1; i <= k; i++){printf("%d %d\n",ans[i].l,ans[i].r);}}}return 0;
}这篇关于ural Minimal Coverage (区间覆盖)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
