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,82设置一个变量表示已经覆盖到的区域。再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，右端点最大的线段在加入，直到已经覆盖全部的区域3过程:假设第一步加入1,4，那么下一步能够选择的有2,6，3,5，3,6，3,7，由于7最大，所以下一步选择3,7，最后一步只能选择6,8，这个时候刚好达到了8退出，所选区间为34贪心证明:需要最少的线段进行覆盖，那么选取的线段必然要尽量长，而已经覆盖到的区域之前的地方已经无所谓了，（可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方），那么真正能够使得线段更成的是右端点，左端点没有太大的意义，所以选择右端点来覆盖例题：Intervals(/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 nonintersecting 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 nonintersecting 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 nonintersecting 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 areaint l,r;amaxn;int cmp(area x,area y)if(x.l=y.l)return x.ry.r;return x.ly.l;int main()int ans,la,lb,n,i;scanf(%d,&n);for(i=1;iai.r)swap(ai.l,ai.r);sort(a+1,a+n+1,cmp);la=a1.l;lb=a1.r;for(i=2;ilb)printf(%d %dn,la,lb);la=ai.l;lb=ai.r;else lb=max(lb,ai.r);printf(%d %dn,la,lb);return 0;例题：校门外的树(/problem/show?pid=1047)数据加强：1=L=109;1=n=200000;#includeusing namespace std;const int maxn=100+20;struct areaint l,r;amaxn;int cmp(area x,area y)if(x.l=y.l)return x.ry.r;return x.ly.l;int main()int ans,la,lb,n,i,L;scanf(%d%d,&L,&n);for(i=1;iai.r)swap(ai.l,ai.r);sort(a+1,a+n+1,cmp);ans=L+1;la=a1.l;lb=a1.r;for(i=2;ilb)ans-=lb-la+1;la=ai.l;lb=ai.r;else lb=max(lb,ai.r);ans-=lb-la+1;coutansendl;return 0;喷水装置（二）(/JudgeOnline/problem.php?pid=12)描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。输入第一行输入一个正整数N表示共有n次测试数据。每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。输出每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。如果不存在一种能够把整个草坪湿润的方案，请输出0。样例输入22 8 61 14 52 10 64 56 5样例输出12思路：对于输入的每个点,先用勾股定理求出能覆盖住矩形的起点和终点,然后进行一次排序,如果最小的起点和最大的终点都不能超过矩形的长度范围,则必定无解,取出起始点最靠前的点,然后记录下这个点的终点,遍历这个起点到终点范围内的所有其他的点,并挑选其中终点最靠后的那个点作为下一个终点的位置,并且计数器加一,继续向后遍历,如果有区间接不上,则表明无解,成功遍历到矩形最后,则直接输出计数器的值#include#include#include#includeusing namespace std;const int maxn=10000+10;struct areadouble l,r;amaxn;int cmp(area x,area y)if(x.l=y.l)return x.ry.r;else return x.ly.l;int main()int t,n,w,flag,i,tot,x,ans,pos;double h,tmp,lb,r;scanf(%d,&t);while(t-)scanf(%d%d%lf,&n,&w,&h);h=h/2;/矩形的高 tot=0;/共tot个矩形覆盖 for(i=1;i0)a+tot.l=max(0.0,x*1.0-tmp);atot.r=x*1.0+tmp;sort(a+1,a+tot+1,cmp);ans=0; flag=1;pos=1;lb=0;/前pos个区间能覆盖的最大区间 for(;lbw;)tmp=0;for(i=pos;ai.l=lb&ilb)ans+;/增加一个喷头 lb=tmp;/更新lb pos=i;/更新pos else /无法往后覆盖 flag=0;break;if(flag)printf(%dn,ans);else printf(0n);return 0;情形2：最大不相交区间数问题数轴上有n个区间ai,bi，要求选择尽量多个区间，使得这些区间两两没有公共点。贪心策略：按照b1=b2a2。 此时区间2包含区间1。这种情况下显然不会选择区间2，因为选择区间1会留下更多的剩余空间。不仅区间2如此，以后所有区间中只要有一个 i 满足a1 ai，i 都不要选。即此种情况下，选择区间1是明智的，与策略一致。2、排除情况1后，一定有a1=a2=a3。例题：线段覆盖（/problem/show?pid=1791）已知数轴上0N10000条线段。每条线段按照端点Ai和Bi（AiBi,i=1.N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现删除最少数目的线段，使得余下的任意两条线段不相交。输入输出格式输入格式：第一行为一整数N。接下来有N行，每行包含两个整数 (Ai 和 Bi), 用空格隔开。输出格式：整数p，即删除后余下的线段数。输入输出样例输入样例#1：3 6 3 1 3 2 5 输出样例#1：2思路：贪心思想，时间复杂度O(nlog(n)1. 数据给出个端点可能逆序，需判断处理。2. 排序，将每一个区间按右端点进行递增顺序排列3.第一个区间必可保留，记录保留区间的最大右边界为pos,遍历区间i，如果ai.lpos，则可保留区间增加，并且pos更新为ai.r。#include#define MaxInt 100000using namespace std;const int maxn=10000+20;struct lineint l,r;amaxn;int n;int cmp(line x,line y)return x.ry.r;int main()int i;scanf(%d,&n);for(i=1;iai.r)swap(ai.l,ai.r);sort(a+1,a+n+1,cmp);int ans=1,pos=a1.r;for(i=2;i=pos)ans+;pos=ai.r;printf(%d,ans);return 0;情形3：区间选点问题。数轴上有n个闭区间ai,bi。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。贪心思想：先按b从小到大进行排序，再选择b0作为选点pos，如果出现aipos，则以bi作为pos，再按照这样的方式迭代。直至所有区间遍历完。找点(/JudgeOnline/problem.php?pid=891)描述上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？输入多组测试数据。每组数据先输入一个N，表示有N个闭区间（N100)。接下来N行，每行输入两个数a，b(0ab100），表示区间的两个端点。输出输出一个整数，表示最少需要找几个点。样例输入41 52 41 42 331 23 45 612 2样例输出131#include#include#include#includeusing namespace std;const int maxn=100+10;struct areaint l,r;amaxn;int cmp(area x,area y)if(x.r=y.r)return x.ly.l;else return x.ry.r;int main()int n,i,pos,ans;while(scanf(%d,&n)!=EOF)for(i=1;i=n;i+)scanf(%d%d,&ai.l,&ai.r);sort(a+1,a+n+1,