AcWing 362. 区间

听书上说有贪心 + 数据结构的做法,研究了一下。

朴素贪心

考虑把所有线段按照右端点 \(b\) 从小到大排序,依次考虑每一条线段的要求:

  • 如果已经满足要求则跳过
  • 否则尽量选择靠后的数(因为之后的线段的右端点都在这条线段的右边,这样容错更高)

所以,我们可以建一个数组,\(d[i]\) 表示 \(i\) 数字是否选择(填\(1\)\(0\)),扫一遍 \([l, r]\) 区间求和,然后从后往前贪心放数即可。

对于每条线段需要 \(O(r - l + 1)\)。所以最坏情况下 \(O(n ^ 2)\)。但是轻松 \(52ms\) 过了。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n, d[N], c[N];
struct Seg{
    int a, b, c;
    bool operator < (const Seg &x) const {
        return b < x.b;
    }
}e[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e + 1, e + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = e[i].a, r = e[i].b, cnt = e[i].c;
        for (int j = l; j <= r; j++)
            cnt -= d[j];
        if(cnt > 0) {
            for (int j = r; j >= l && cnt; j--)
                if(!d[j]) cnt--, ans++, d[j] = 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

优化

考虑用数据结构优化。

发现我们需要三个操作:

  • 询问 \([l, r]\) 区间的数字个数
  • 将值为 \(x\) 的位置 \(+1\)
  • 从后往前,找到比当前位置靠前的下一个 \(0\) 的位置。
  1. 前两个就是 “区间求和,单调修改”,典型的树状数组。$O(nlog_250000) $

  2. 第三种操作,可以用并查集优化。为什么可以确保时间复杂度呢?对于每一条线段,最多只有一次会枚举到 \(1\) (即开始的那一次),之后每次枚举都会枚举到 \(0\) 的位置,即\(d[i] = 0\),然后把它变成 \(1\),而以后就不会访问到了。而一共有 \(50000\) 个值,所以复杂度是 \(O(50000log_n)\)

\(33ms\)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50001;
int n, d[N], c[N], f[N];
struct Seg{
    int a, b, c;
    bool operator < (const Seg &x) const {
        return b < x.b;
    }
}e[N];
// 树状数组
int inline ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += c[x];
    return res;
}

void inline add(int x) {
    for (; x < N; x += x & -x) c[x]++;
}
// 并茶集:find(x) 表示找到 <= x 中最大的一个是 0 的数
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < N; i++) f[i] = i;
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e + 1, e + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = e[i].a, r = e[i].b, cnt = e[i].c;
        // 取 [l, r] 选了多少个数
        cnt -= ask(r) - ask(l - 1);
        if(cnt > 0) {
            for (int j = r; j >= l && cnt; ) {
                // d[j] == 1 的情况每条线段至多出现一次
                if(!d[j]) {
                    cnt--, ans++, d[j] = 1;
                    // j 被标记成 1 了,要指向 find(j - 1)
                    f[j] = j - 1;
                    // 维护树状数组
                    add(j);
                };
                if(find(j) != j) j = f[j];
                else j--;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

AcWing 362. 区间

上一篇:Win10蓝牙鼠标老是断连卡顿的解决方法


下一篇:让HCL在WIN10上运行