noip算法：三类基于贪心思想的区间覆盖问题.doc

三类基于贪心思想的区间覆盖问题情形1：区间完全覆盖问题描述：给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖样例：区间长度8，可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]解题过程:1将每一个区间按照左端点递增顺序排列，拍完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]2设置一个变量表示已经覆盖到的区域再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，右端点最大的线段在加入，直到已经覆盖全部的区域3过程:假设第一步加入[1,4]，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]，由于7最大，所以下一步选择[3,7]，最后一步只能选择[6,8]，这个时候刚好达到了8退出，所选区间为34贪心证明:需要最少的线段进行覆盖，那么选取的线段必然要尽量长，而已经覆盖到的区域之前的地方已经无所谓了，（可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方），那么真正能够使得线段更成的是右端点，左端点没有太大的意义，所以选择右端点来覆盖例题：Intervals(http://poj.org/problem?id=1089DescriptionThere is given the series of n closed intervals [ai; bi], where i=1,2,...,n. The sum of those intervals may be represented as a sum of closed pairwise non−intersecting intervals. The task is to find such representation with the minimal number of intervals. The intervals of this representation should be written in the output file in acceding order. We say that the intervals [a; b] and [c; d] are in ascending order if, and only if a <= b < c <= d. Task Write a program which: reads from the std input the description of the series of intervals, computes pairwise non−intersecting intervals satisfying the conditions given above, writes the computed intervals in ascending order into std outputInputIn the first line of input there is one integer n, 3 <= n <= 50000. This is the number of intervals. In the (i+1)−st line, 1 <= i <= n, there is a description of the interval [ai; bi] in the form of two integers ai and bi separated by a single space, which are respectively the beginning and the end of the interval,1 <= ai <= bi <= 1000000.OutputThe output should contain descriptions of all computed pairwise non−intersecting intervals. In each line should be written a description of one interval. It should be composed of two integers, separated by a single space, the beginning and the end of the interval respectively. The intervals should be written into the output in ascending order.Sample Input55 61 410 106 98 10Sample Output1 45 10题意：求区间最大覆盖#include #include #include #include #include #include using namespace std;const int maxn=50000+20;struct area{ int l,r;}a[maxn];int cmp(area x,area y){ if(x.l==y.l)return x.ra[i].r)swap(a[i].l,a[i].r); } sort(a+1,a+n+1,cmp); la=a[1].l;lb=a[1].r; for(i=2;i<=n;i++){ if(a[i].l>lb){ printf("%d %d\n",la,lb); la=a[i].l;lb=a[i].r; } else { lb=max(lb,a[i].r); } } printf("%d %d\n",la,lb); return 0;}例题：校门外的树(https://www.luogu.org/problem/show?pid=1047)数据加强：1<=L<=10^9;1<=n<=200000;#includeusing namespace std;const int maxn=100+20;struct area{ int l,r;}a[maxn];int cmp(area x,area y){ if(x.l==y.l)return x.ra[i].r)swap(a[i].l,a[i].r); } sort(a+1,a+n+1,cmp); ans=L+1;la=a[1].l;lb=a[1].r; for(i=2;i<=n;i++){ if(a[i].l>lb){ ans-=lb-la+1; la=a[i].l;lb=a[i].r; } else { lb=max(lb,a[i].r); } } ans-=lb-la+1; cout<#include#include#includeusing namespace std;const int maxn=10000+10;struct area{ double l,r;}a[maxn];int cmp(area x,area y){ if(x.l==y.l)return x.r0){ a[++tot].l=max(0.0,x*1.0-tmp); a[tot].r=x*1.0+tmp; } } sort(a+1,a+tot+1,cmp); ans=0; flag=1; pos=1; lb=0;//前pos个区间能覆盖的最大区间 for(;lblb){ ans++;//增加一个喷头 lb=tmp;//更新lb pos=i;//更新pos } else {//无法往后覆盖 flag=0; break; 。