A.华华听月月唱歌

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

题意：

月月唱歌超级好听的说！华华听说月月在某个网站发布了自己唱的歌曲，于是把完整的歌曲下载到了U盘里。然而华华不小心把U盘摔了一下，里面的文件摔碎了。月月的歌曲可以看成由1到N的正整数依次排列构成的序列，它现在变成了若干个区间，这些区间可能互相重叠。华华想把它修复为完整的歌曲，也就是找到若干个片段，使他们的并集包含1到N（注意，本题中我们只关注整数，见样例1）。但是华华很懒，所以他想选择最少的区间。请你算出华华最少选择多少个区间。因为华华的U盘受损严重，所以有可能做不到，如果做不到请输出-1。

思路：

左端点排序，从左端点最多超出当点右端点1的段中选右端点最远的。

判断是否能覆盖全部端点。

代码：

#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");

    else

        printf("%d\n", res);

    return 0;

}

巴特西

A.华华听月月唱歌

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

题意：

思路：

代码：

最新文章

热门文章