区间覆盖求调
查看原帖
区间覆盖求调
833124
BIOS楼主2023/5/27 12:31
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2.5e4 + 10;
struct node
{
    int l, r;
    bool operator<(const node &a) const
    {
        return l < a.l;
    }
} s[N];
int main()
{
    int st, ed;
    int n, k;
    cin >> n >> k;
    st = 1, ed = k;
    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        s[i] = {l, r};
    }
    sort(s, s + n);
    int res = 0;
    int r = -2e9;
    for (int i = 0; i < n; i++)
    {
        int j = i;
        while (j < n && s[j].l <= st + 1)
            r = max(r, s[j].r), j++;
        if (r < st)
            break;
        res++;
        if (r >= ed)
        {
            cout << res << endl;
            return 0;
        }
        i = j - 1;
        st = r;
    }
    cout << -1 << endl;
}

WA on#5#6 不知道为什么,我看except输出,有一个应该输出-1的点我都没过,算法哪里有问题?

2023/5/27 12:31
加载中...