1730: 數區間
時間限制: 1 Sec 內存限制: 128 MB
[提交][狀態][討論版]
題目描述
月月唱歌超級好聽的說！華華聽說月月在某個網站發布了自己唱的歌曲，于是把完整的歌曲下載到了U盤里。然而華華不小心把U盤摔了一下，里面的文件摔碎了。月月的歌曲可以看成由1到N的正整數依次排列構成的序列，它現在變成了若干個區間，這些區間可能互相重疊。華華想把它修復為完整的歌曲，也就是找到若干個片段，使他們的并集包含1到N（注意，本題中我們只關注整數，見樣例1）。但是華華很懶，所以他想選擇最少的區間。請你算出華華最少選擇多少個區間。因為華華的U盤受損嚴重，所以有可能做不到，如果做不到請輸出-1。

輸入
第一行兩個正整數N、M，表示歌曲的原長和片段的個數。
接下來M行，每行兩個正整數L、R表示第i的片段對應的區間是[L,R]。
單組數據輸入
輸出
如果可以做到，輸出最少需要的片段的數量，否則輸出-1。
樣例輸入

10 5 1 1 2 5 3 6 4 9 8 10

樣例輸出

4

提示
1≤L≤R≤1e9,1≤N≤1e9,1≤M≤1e5
Ac_code:

/*
解題思路：
看一下數據范圍肯定，肯定不能直接暴。
要組成一個1-n的區間，那么首先給的區間里肯定要有n啊
然后要篩出最少的區間來達到目的。
毫無疑問先對給的區間按區間左值s從小到大，s相同按短的優先，排個序。
首先要選一個區間，然后看它后面的區間是否可以完全替代它。要替代一個區間，那么就要看一個區間有用部分能不能完全被另一個區間取代。怎么定義一個區間的有用的部分呢？
我們知道如果一個區間有某個部分，其他區間沒有，那么它這部分至少在構成一個1-n的區間過程中是有用的。
我把最近一個選定的區間有用部分定義為：l----r
與它比較的區間設為**:s2—e2**
下面我們一個個分情況討論(畫的有點抽象~)：
先來看后面的區間不能替代最近一個選定的區間的情況：

很明顯只要e2 <=r,那么對于s2–e2完全可以略過不選。
再看不能達到目標的情況：

也很明顯r到s2之間有一段無法填補，因為我們是排好序的，當前出現這種情況，后面不管怎么選都這樣肯定不能構成一段1–n的區間。
同時我們可以從這里看出，r+1=s2的話，s2—e2要選做選定的區間，后面有沒有其他區間將它替換先不管，選定s2–e2,那么最近有用的區間就要更新，即l =s2,r = e2
再看要選定當前與l–r比較的區間：

此時s2—e2有一部分相對l—r有用，選它！！
更新l = r+1，r = e2
再看要丟棄上一個選定區間的情況：
（強調一下l不一定是給定區間的最左端，l–r只是最近’‘選定’'區間的有用部分）

很明顯，l–r完全可以由s2—e2代替。
so，丟棄l，r所在區間，選定s2–e2,
因為有用的部分最左端沒有變， l可以不更新，右端可能變了，r = e2

*/

#include <bits/stdc++.h>using namespace std; const int maxn = 1e5+5; struct MyRange {int s;int e;bool operator<(const MyRange x)const{if(s == x.s)return e < x.e;return s < x.s;} } a[maxn]; int main() {int n,m;scanf("%d%d",&n,&m);int flag = 0;for(int i = 0; i < m; i++){scanf("%d%d",&a[i].s,&a[i].e);if(a[i].e == n){flag = 1;}}if(!flag){puts("-1");return 0;}sort(a,a+m);int ans = 1;int l = a[0].s,r = a[0].e;for(int i = 1; i < m; i++){if(a[i].e <= r){continue;}if(a[i].s > r+1){puts("-1");return 0;}if(a[i].s == r+1){ans++;l = r+1;r = a[i].e;}else if(l<a[i].s&&r>a[i].s&&r<a[i].e){ans++;l = r+1;r = a[i].e;}else if(l>=a[i].s&&r<=a[i].e){r = a[i].e;}}printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的1730: 数区间(线段覆盖，贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。