題意：
? ? ? 給你一個區(qū)間[0,m]和一些小的區(qū)間[l,r]讓你選擇最少的小區(qū)間個數(shù)去把整個區(qū)間覆蓋起來。


思路：
? ? ? 算是比較經(jīng)典的貪心題目吧（經(jīng)典于難度沒什么對應(yīng)關(guān)系），大體思路可以是這樣，我們先把所有的區(qū)間按照起點從小到大排序，然后我們定義一個當前覆蓋位置pos,初始是0，也就是[0,m]的最左端，然后我們從小區(qū)間中找到一個可以覆蓋pos點并且右端點最遠的一個（記得sum++）,然后把最遠的這個右端點作為當前的pos，繼續(xù)找下一個，至于實現(xiàn)，我是自己寫的，可能寫的不是很簡潔，不知道網(wǎng)上有沒有簡潔點的，如果沒有就講究看下我的吧，具體細節(jié)看代碼。



#include<stdio.h>
#include<algorithm>

#define N 110000

using namespace std;

typedef struct
{
? ?int l ,r;
}EDGE;

EDGE edge[N] ,Ans_edge[N];

bool camp(EDGE a, EDGE b)
{
? ?return a.l < b.l;
}

int main ()
{
? ?int m ,nowid ,i ,t ,a ,b;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d" ,&m);
? ? ? nowid = 0;
? ? ? while(1)
? ? ? {
? ? ? ? ?scanf("%d %d" ,&a ,&b);
? ? ? ? ?if(!a && !b) break;
? ? ? ? ?if(a > m || b < 0) continue;
? ? ? ? ?++nowid;
? ? ? ? ?edge[nowid].l = a ,edge[nowid].r = b;
? ? ? }
? ? ? sort(edge + 1 ,edge + nowid + 1 ,camp);
? ? ? int Ans = 0 ,pos = 0 ,max = 0 ,mkid = 0;
? ? ? for(i = 1 ;i <= nowid ;i ++)
? ? ? {
? ? ? ? ?if(pos > edge[i].r) continue;
? ? ? ? ?if(edge[i].l <= pos)
? ? ? ? ?{
? ? ? ? ? ? if(max < edge[i].r) {max = edge[i].r ,mkid = i;}
? ? ? ? ? ? if(i == nowid)
? ? ? ? ? ? {
? ? ? ? ? ? ? ?if(max < m){Ans = 0 ;break;}
? ? ? ? ? ? ? ?Ans_edge[++Ans] = edge[mkid];
? ? ? ? ? ? } ??
? ? ? ? ?}
? ? ? ? ?else
? ? ? ? ?{
? ? ? ? ? ? if(!max){Ans = 0; break;}
? ? ? ? ? ? pos = max;
? ? ? ? ? ? max = 0 ,Ans ++ ,i --;
? ? ? ? ? ? Ans_edge[Ans] = edge[mkid];
? ? ? ? ? ? if(pos >= m) break;
? ? ? ? ?}
? ? ? }
? ? ? printf("%d\n" ,Ans);
? ? ? for(i = 1 ;i <= Ans ;i ++)
? ? ? printf("%d %d\n" ,Ans_edge[i].l ,Ans_edge[i].r);
? ? ? if(t) printf("\n");
? ?}
? ?return 0;
}
? ?
? ? ??
? ? ? ? ? ??
? ? ? ? ? ??
? ? ??
? ? ??
? ?
? ?
? ??

總結(jié)

以上是生活随笔為你收集整理的UVA10020(最小区间覆盖)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。