AcWing 295. 清理班次

这题显然跟区间覆盖是一样的，而且值域在 \(1000000\) 以内，不用离散化，直接贪心求解即可。

具体地：设 \(nxt[i]\) 为从值域 \(i\) 出发，能到达最远的右端点。

一段段地跳，直到跳到终点 \(T\) 或者跳不动了。

\(Tips\)：注意这里是点覆盖，而区间覆盖是边覆盖，要注意跳的细节。

#include <iostream>

using namespace std;

const int N = 1000001;

int n, m, p = 1, ans = 0, nxt[N];

int main() {

    scanf("%d%d", &m, &n);

    for (int i = 0, l, r; i < m; i++)

        scanf("%d%d", &l, &r), nxt[l] = max(nxt[l], r);

    for (int i = 1; i <= n; i++) nxt[i] = max(nxt[i], nxt[i - 1]);

    while(p <= n && nxt[p] >= p) p = nxt[p] + 1, ans++;

    printf("%d\n", p <= n ? -1 : ans);

    return 0;

}

巴特西

AcWing 295. 清理班次

最新文章

热门文章