鏈接：https://ac.nowcoder.com/acm/contest/392/A

題意：

月月唱歌超級好聽的說！華華聽說月月在某個網(wǎng)站發(fā)布了自己唱的歌曲，于是把完整的歌曲下載到了U盤里。然而華華不小心把U盤摔了一下，里面的文件摔碎了。月月的歌曲可以看成由1到N的正整數(shù)依次排列構(gòu)成的序列，它現(xiàn)在變成了若干個區(qū)間，這些區(qū)間可能互相重疊。華華想把它修復(fù)為完整的歌曲，也就是找到若干個片段，使他們的并集包含1到N（注意，本題中我們只關(guān)注整數(shù)，見樣例1）。但是華華很懶，所以他想選擇最少的區(qū)間。請你算出華華最少選擇多少個區(qū)間。因?yàn)槿A華的U盤受損嚴(yán)重，所以有可能做不到，如果做不到請輸出-1。

思路：

左端點(diǎn)排序，從左端點(diǎn)最多超出當(dāng)點(diǎn)右端點(diǎn)1的段中選右端點(diǎn)最遠(yuǎn)的。

判斷是否能覆蓋全部端點(diǎn)。

代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 1e5 + 10;struct Node {int _l;int _r;bool operator < (const Node & that) const{return this->_l < that._l;} }node[MAXN];int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 1;i <= m;i++)scanf("%d%d", &node[i]._l, &node[i]._r);sort(node + 1, node + 1 + m);int l = 0, r = 0, res = 0, len = 0;int flag = 1;for (int i = 1;i <= m;i++){if (node[i]._l <= r + 1){len = max(len, node[i]._r - r);continue;}if (len == 0){flag = 0;break;}r = r + len;len = 0;res++;i--;//cout << r << endl;if (r >= n){len = 0;break;}}if (len > 0){r += len;res++;}if (!flag || r < n)printf("-1\n");elseprintf("%d\n", res);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/YDDDD/p/10504754.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的A.华华听月月唱歌的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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