NOIP算法：三類基于貪心思想的區(qū)間覆蓋問題

1、三類基于貪心思想的區(qū)間覆蓋問題情形 1：區(qū)間完全覆蓋問題描述：給定一個長度為 m 的區(qū)間，再給出 n 條線段的起點和終點（注意這里是閉區(qū)間），求最少使用多少條線段可以將整個區(qū)間完全覆蓋樣例：區(qū)間長度 8，可選的覆蓋線段2,6,1,4,3,6,3,7,6,8,2,4,3,5解題過程 :1 將每一個區(qū)間按照左端點遞增順序排列，拍完序后為 1,4 ， 2,4 ， 2,6 ， 3,5 ， 3,6 ， 3,7 ， 6,82 設置一個變量表示已經(jīng)覆蓋到的區(qū)域。再剩下的線段中找出所有左端點小于等于當前已經(jīng)覆蓋到的區(qū)域 的右端點的線段中，右端點最大的線段在加入，直到已經(jīng)覆蓋全部的區(qū)域3 過程 : 假設第一步加

2、入 1,4 ，那么下一步能夠選擇的有2,6 ， 3,5 ， 3,6 ， 3,7 ，由于 7 最大，所以下一步選擇 3,7 ，最后一步只能選擇6,8 ，這個時候剛好達到了 8 退出，所選區(qū)間為34 貪心證明 :需要最少的線段進行覆蓋，那么選取的線段必然要盡量長，而已經(jīng)覆蓋到的區(qū)域之前的地方已經(jīng)無所謂了，（可以理解成所有的可以覆蓋的左端點都是已經(jīng)覆蓋到的地方），那么真正能夠使得線段更成的是右端點，左端點沒有太大的意義，所以選擇右端點來覆蓋例題： Intervals（/problem?id=1089DescriptionThere is given the series o

3、f n closed intervals ai; bi, where i=1,2,.,n.The sum ofthose 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

4、 acceding order. We say that the intervals a; b and c; d are in ascending order if, and only if a <= b < c <= d.TaskWrite 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

5、, 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

6、 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 shoul

7、d 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 題意：求區(qū)間最大覆蓋 #include <iostream>#include <vector>#inclu

8、de <algorithm>#include <cstring>#include <cstdio>#include <cmath>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.r<y.r;return x.l<y.l;int main()int ans,la,lb,n,i;scanf("%d",&n);for(i=1;i<=n;

9、i+)scanf("%d%d",&ai.l,&ai.r);if(ai.l>ai.r)swap(ai.l,ai.r);sort(a+1,a+n+1,cmp);la=a1.l;lb=a1.r;for(i=2;i<=n;i+)if(ai.l>lb)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/sh

10、ow?pid=1047)數(shù)據(jù)加強：1<=L<=10A9;1<=n<=200000;#include<bits/stdc+.h>using 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.r<y.r;return x.l<y.l;int main()int ans,la,lb,n,i,L;scanf("%d%d",&L,&n);for(i=1;i<=n

11、;i+)scanf("%d%d",&ai.l,&ai.r);if(ai.l>ai.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;i<=n;i+)if(ai.l>lb)ans-=lb-la+1;la=ai.l;lb=ai.r;else lb=max(lb,ai.r);ans-=lb-la+1;cout<<ans<<endl;return 0;噴水裝置(二) (描述有一塊草坪，橫向長 w,縱向長為h,在它的橫向中心線上不同位置處

12、裝有n(n<=10000)個點狀的噴水裝置，每個噴水裝置 i 噴水的效果是讓以它為中心半徑為 Ri 的圓都被潤濕。請在給出的噴水裝置中選擇盡量少的噴水裝置，把整個草坪全部潤濕。輸入第一行輸入一個正整數(shù)N 表示共有 n 次測試數(shù)據(jù)。每一組測試數(shù)據(jù)的第一行有三個整數(shù)n,w,h , n表示共有n個噴水裝置，w表示草坪的橫向長度，h表示草坪的縱向長度。隨后的 n 行，都有兩個整數(shù)xi 和 ri,xi 表示第 i 個噴水裝置的的橫坐標(最左邊為0)，ri 表示該噴水裝置能覆蓋的圓的半徑。輸出每組測試數(shù)據(jù)輸出一個正整數(shù)，表示共需要多少個噴水裝置，每個輸出單獨占一行。如果不存在一種能夠把整個草坪濕潤的

13、方案，請輸出 0 。樣例輸入22 8 61 14 52 10 64 56 5樣例輸出12思路：對于輸入的每個點 , 先用勾股定理求出能覆蓋住矩形的起點和終點 , 然后進行一次排序, 如果最小的起點和最大的終點都不能超過矩形的長度范圍 , 則必定無解, 取出起始點最靠前的點 , 然后記錄下這個點的終點 , 遍歷這個起點到終點范圍內(nèi)的所有其他的點 , 并挑選其中終點最靠后的那個點作為下一個終點的位置并且計數(shù)器加一, 繼續(xù)向后遍歷, 如果有區(qū)間接不上, 則表明無解, 成功遍歷到矩形最后, 則直接輸出計數(shù)器的值#include<cstdio>#include<cstdlib>#

14、include<iostream>#include<algorithm>using 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.r<y.r;else return x.l<y.l;int main()int t,n,w,flag,i,tot,x,ans,pos;double h,tmp,lb,r;scanf("%d",&t);while(t-)scanf(&qu

15、ot;%d%d%lf",&n,&w,&h);h=h/2;/矩形的高tot=0; 共tot個矩形覆蓋for(i=1;i<=n;i+)scanf("%d%lf",&x,&r);tmp=sqrt(r*r-h*h);計算矩形的寬if(tmp>0)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個區(qū)間能覆蓋的最大區(qū)間for(;lb<w;)tmp=0;for(i=pos;ai.l

16、<=lb&&i<=tot;i+)tmp=max(tmp,ai.r);/左邊界在lb以內(nèi)能覆蓋到的最遠距離if(tmp>lb)ans+;/增加一個噴頭lb=tmp;/ 更新 lb pos=i;/ 更新 poselse /無法往后覆蓋flag=0； break;if(flag)printf("%dn",ans);else printf("0n");return 0;情形2:最大不相交區(qū)間數(shù)問題數(shù)軸上有n個區(qū)間ai,bi,要求選擇盡量多個區(qū)間，使得這些區(qū)間兩兩沒有公共點。貪心策略：按照b1<=b2<=b3的方式排序

17、，然后從前向后遍歷，每當遇到可以加入集合的區(qū)間，就把它加入集合。（集合代表解的集合）證明：我們對a1,a2的關系分以下幾種情況考慮：1、a1>a2o 此時區(qū)間2包含區(qū)間1。這種情況下顯然不會選擇區(qū)間2,因為選擇區(qū)間1會留下更多的剩余空間。不僅區(qū)間2如此，以后所有區(qū)間中只要有一個i滿足a1 > ai , i都不要選。即此種情況下，選擇區(qū)間1是明智的，與策略一致。2、排除情況1后，一定有a1<=a2<=a3。al區(qū)間7 al*區(qū)間工al* bl例題：線段覆蓋( /problem/show?pid=1791 )已知數(shù)軸上0<N&l

18、t;10000 條線段。每條線段按照端點 Ai 和 Bi (Ai<>Bi,i=1.N)定義。端點坐標在( -999 ， 999)內(nèi)，坐標為整數(shù)。有些線段可能相交。編程實現(xiàn)刪除最少數(shù)目的線段，使得余下的任意兩條線段不相交。輸入輸出格式輸入格式：第一行為一整數(shù)No接下來有N行，每行包含兩個整數(shù)(Ai和Bi),用空格隔開。輸出格式：整數(shù)p,即刪除后余下的線段數(shù)。輸入輸出樣例輸入樣例 #1：36 31 32 5輸出樣例 #1：2思路：貪心思想，時間復雜度O(nlog(n)1. 數(shù)據(jù)給出個端點可能逆序，需判斷處理。2. 排序，將每一個區(qū)間按右端點進行遞增順序排列3. 第一個區(qū)間必可保留，記錄

19、保留區(qū)間的最大右邊界為 pos, 遍歷區(qū)間 i ，如果 ai.l>pos ，則可保留區(qū)間增加，并且 pos 更新為 ai.r 。#include<bits/stdc+.h>#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.r<y.r;int main()int i;scanf("%d",&n);for(i=1;i<=n;i+)scanf

20、("%d%d",&ai.l,&ai.r);if(ai.l>ai.r)swap(ai.l,ai.r);sort(a+1,a+n+1,cmp);int ans=1,pos=a1.r;for(i=2;i<=n;i+)if(ai.l>=pos)ans+;pos=ai.r;printf("%d",ans);return 0;情形3：區(qū)間選點問題。數(shù)軸上有 n 個閉區(qū)間 ai,bi 。取盡量少的點，使得每個區(qū)間內(nèi)都至少有一個點(不同區(qū)間內(nèi)含的點可以是同一個)。貪心思想：先按b 從小到大進行排序，再選擇 b0 作為選點 pos ，如果出現(xiàn)ai>pos ，則以 bi 作為 pos ，再按照這樣的方式迭代。直至所有區(qū)間遍歷完。區(qū)間工找點( ;上數(shù)學課時，老師給了LYH一些閉區(qū)間，讓他取盡量少的點，使得每個閉區(qū)間內(nèi)至少有一個點。但是這幾天LYH太忙了，你們幫幫他嗎？ 輸入多組測試數(shù)據(jù)。每組數(shù)據(jù)先輸入一個 N,表示有N個閉區(qū)間(NK 100)。接下來N行，每行輸入兩個數(shù) a, b(0<a<b<100),表示區(qū)間的兩個端點。 輸出輸出一個整數(shù)，表示最少需要找?guī)讉€點。樣例輸入41 52 41 42 331 23 45 612 2樣例輸出131#include<cstdio>