【思维】Codeforces 1555E Boring Segments
|
358
|
思维题
|
tdiant

题意

在一个 [1,m) 的数轴上有 n 条线段，第 i 条覆盖的范围是[li, ri)，权值是wi。

现在希望我们能从这n个线段里挑出一些线段，这些线段能够覆盖数轴上[1,m)所有点。问在这些所有可能的选法里，所选线段权值最大的那个的权值减去最小的权值，这个差最小能是多少。

思路

用快慢指针实现扫描功能

首先将这n个线段排序，这里可以用快慢指针去扫这些线段。慢指针i代表至左到哪里，快指针j代表选的最后一个是哪个线段。

这时需要注意一件事：对于i到j这些线段，我去讨论在这之间的线段取不取是没意义的，因为他不会影响最大值减最小值的结果，不影响答案。影响答案的是i和j。

假如我开了一个一维数组记录这个点被覆盖了几次，j往后挪一下，我们就把第j个线段覆盖的区域上的点的值全部+1，直到j这次挪动把所有点都覆盖上了。
全部覆盖的时候，跟历史结果取最小。
i往后挪之前，先把这个线段上对应区间的点的值都-1，然后i++。

这里有个细节：如果j碰到头了还不能覆盖全部点，那这个快慢指针扫描就可以停止了，因为i之后往后挪也搜不到答案了，再搜没意义了，直接输出答案就完事了。

用线段树维护区间最小值

这里还有两个问题：

  1. 怎么实现区间所有点都加一
  2. 我怎么知道[1,m)是不是都被覆盖了。

方法很简单，我们开个线段树维护区间最小值就行了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

const int N = 4e5 + 233;

int n, m;
typedef struct {
    int l, r, w;
} ii;

ii lines[N];

struct {
    int d, b;
} seg[(N << 4)];

void segDownLazy(int p) {
    if (seg[p].b == 0) return;
    seg[p << 1].d += seg[p].b;
    seg[(p << 1) + 1].d += seg[p].b;
    seg[p << 1].b += seg[p].b;
    seg[(p << 1) + 1].b += seg[p].b;
    seg[p].b = 0;
}

void build(int s, int t, int p) {
    if (s == t) {
        seg[p].d = 0;
        return;
    }
    int mid = (s + t) >> 1;
    build(s, mid, p << 1);
    build(mid + 1, t, (p << 1) + 1);
    seg[p].d = seg[p << 1].d + seg[(p << 1) + 1].d;
}

void segUpdateMin(int l, int r, int c, int s, int t, int p) {
    if (l <= s && t <= r) {
        seg[p].d += c;
        seg[p].b += c;
        return;
    }
    int mid = (s + t) >> 1;
    //标记下传
    if (s < t) segDownLazy(p);
    if (l <= mid) segUpdateMin(l, r, c, s, mid, p << 1);
    if (r > mid) segUpdateMin(l, r, c, mid + 1, t, (p << 1) + 1);
    seg[p].d = min(seg[p << 1].d, seg[(p << 1) + 1].d);
}

int queryMin(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return seg[p].d;
    int mid = (s + t) >> 1;
    //懒标记下传
    segDownLazy(p);
    int mx = seg[p].d;
    if (l <= mid) mx = min(mx, queryMin(l, r, s, mid, p << 1));
    if (r > mid) mx = min(mx, queryMin(l, r, mid + 1, t, (p << 1) + 1));
    return mx;
}

bool cmp(ii a, ii b) {
    return a.w < b.w;
}

void solve() {

    sort(lines + 1, lines + 1 + n, cmp);

    int ans = 0x3f3f3f3f;
    for (int i = 1, j = 0; i <= n; i++, j = max(j, i)) {
        while (queryMin(1, m, 1, m, 1) <= 0) {
            j += 1;
            if (j > n) {
                cout << ans << '\n';
                return;
            }
            segUpdateMin(lines[j].l, lines[j].r, 1, 1, m, 1);
        }
        ans = min(ans, (lines[j].w - lines[i].w));
        segUpdateMin(lines[i].l, lines[i].r, -1, 1, m, 1);
    }

    cout << ans << '\n';
}

int main() {

    cin >> n >> m;
    m--;//这里是坑，数轴取值范围是不算m的
    for (int i = 1; i <= n; i++) {
        cin >> lines[i].l >> lines[i].r >> lines[i].w;
        lines[i].r--; //这里是坑，线段取值范围是不算右端点的
    }

    build(1, m, 1);

    solve();

    return 0;
}
上一篇
下一篇