「[NOIP2012 提高组] 借教室」题解

原题目链接：Link。

思路一：完全没有 idea？输出 \(0\)，得到 \(5\text{pts}\)。

思路二：\(O(nm)\) 暴力，用 O2 可以得到 \(60\text{pts}\)。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
template <typename T> void read(T &x) {x = 0; T f = 1; char tem = getchar(); while (tem < '0' || tem > '9') {if (tem == '-') f = -1; tem = getchar();} while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0'; tem = getchar();} x *= f;}
template <typename T> void write(T x) {if (x < 0) {x = -x; putchar ('-');} if (x > 9) write (x / 10); putchar (x % 10 + '0');}

int n, m;
int r[MAXN], d[MAXN], s[MAXN], t[MAXN];
int main() {
    read(n); read(m);
    for (int i = 1; i <= n; i++) read(r[i]);
    for (int i = 1; i <= m; i++) {
        read(d[i]); read(s[i]); read(t[i]);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = s[i]; j <= t[i]; j++) {
            r[j] -= d[i];
            if (r[j] < 0) return printf("-1\n%d\n", i), 0;
        }
    }
    puts("0");
    return 0;
}

思路三：我们可以发现，结果具有单调性。也就是说，天数越大，就越不容易满足。因此，我们可以二分。这是一个奇怪的二分代码：

#include <bits/stdc++.h>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 5;
template <typename T> void read(T &x) {x = 0; T f = 1; char tem = getchar(); while (tem < '0' || tem > '9') {if (tem == '-') f = -1; tem = getchar();} while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0'; tem = getchar();} x *= f;}
template <typename T> void write(T x) {if (x < 0) {x = -x; putchar ('-');} if (x > 9) write (x / 10); putchar (x % 10 + '0');}

int n, m;
int r[MAXN], d[MAXN], s[MAXN], t[MAXN];
int tmp[MAXN];

bool check(int x) {
    for (int i = 1; i <= x; i++) {
        for (int j = s[i]; j <= t[i]; j++) {
            r[j] -= d[i];
            if (r[j] < 0) return false;
        }
    }
    return true;
}
int main() {
    read(n); read(m);
    for (int i = 1; i <= n; i++) {read(r[i]); tmp[i] = r[i];}
    for (int i = 1; i <= m; i++) {
        read(d[i]); read(s[i]); read(t[i]);
    }
    int L = 1, R = m, mid;
    while (L < R) {
        if (check(mid = L + R >> 1)) L = mid + 1;
        else R = mid;
        memcpy(r, tmp, sizeof(tmp));
    }
    if (L != m) printf("-1\n%d\n", L);
    else puts("0");
    return 0;
}

时间复杂度是 \(O(nm \log m)\)（猜测）？尽管这样写只能得到 \(40\text{pts}\)，但也给我们提供了一个二分框架。接下来一个新的问题是，如何优化 check 函数？对于每个订单 \(j\)，相当于把 \(r\) 数组的 \(s_j\) 到 \(t_j\) 全部减去 \(d_j\)，这让我们想到差分。只需要差分完后 \(O(n)\) 计算前缀和即可。AC代码如下：

#include <bits/stdc++.h>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 5;
template <typename T> void read(T &x) {x = 0; T f = 1; char tem = getchar(); while (tem < '0' || tem > '9') {if (tem == '-') f = -1; tem = getchar();} while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0'; tem = getchar();} x *= f;}
template <typename T> void write(T x) {if (x < 0) {x = -x; putchar ('-');} if (x > 9) write (x / 10); putchar (x % 10 + '0');}

int n, m;
int r[MAXN], d[MAXN], s[MAXN], t[MAXN];
int c[MAXN];

bool check(int x) {
    for (int i = 1; i <= x; i++)
        c[s[i]] += d[i], c[t[i] + 1] -= d[i]; // 差分
    for (int i = 1; i <= n; i++) {
        c[i] += c[i - 1]; // 前缀和
        if (c[i] > r[i]) return false;
        // 为什么我们不直接在 r 数组上进行操作呢
        // 因为 check 完后需要将 r 数组还原，这就需要 O(n) 的复杂度
        // 而这样写就不需要还原了
    }
    return true;
}
int main() {
    read(n); read(m);
    for (int i = 1; i <= n; i++) read(r[i]);
    for (int i = 1; i <= m; i++) {
        read(d[i]); read(s[i]); read(t[i]);
    }
    int L = 1, R = m, mid;
    while (L < R) {
        memset(c, 0, sizeof(c));
        if (check(mid = L + R >> 1)) L = mid + 1;
        else R = mid;
    }
    if (L != m) printf("-1\n%d\n", L);
    else puts("0");
    return 0;
}