[NOIP 2011 提高组] 聪明的质监员

题意

给定 n 个矿石，每个矿石有：

重量 w_i
价值 v_i

再给定 m 个区间 [l_i,r_i] 和一个标准值 s。

选定一个阈值 W 后，对每个区间定义：

区间中满足 w_j >= W 的矿石个数
区间中这些矿石价值之和

两者相乘得到这个区间的检验值，所有区间检验值之和记作 y(W)。

要求选择一个 W，使得：

|y(W) - s|

最小，并输出这个最小值。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MAXM = 25;

int n, m;
long long s;
int w[MAXN], v[MAXN];
int L[MAXM], R[MAXM];
int max_w;

void print_int128(__int128 x) {
    if (x == 0) {
        cout << 0 << '\n';
        return;
    }

    if (x < 0) {
        cout << '-';
        x = -x;
    }

    string str;
    while (x > 0) {
        str.push_back(char('0' + x % 10));
        x /= 10;
    }
    reverse(str.begin(), str.end());
    cout << str << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s;

    max_w = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
        max_w = max(max_w, w[i]);
    }

    for (int i = 1; i <= m; i++) {
        cin >> L[i] >> R[i];
    }

    // brute.cpp：小数据暴力。
    // 直接枚举所有可能的 W，按定义计算总检验值 y，
    // 再取 |y-s| 的最小值。
    __int128 ans = -1;

    for (int W = 0; W <= max_w + 1; W++) {
        __int128 total = 0;

        for (int i = 1; i <= m; i++) {
            long long cnt = 0;
            long long sumv = 0;

            for (int j = L[i]; j <= R[i]; j++) {
                if (w[j] >= W) {
                    cnt++;
                    sumv += v[j];
                }
            }

            total += (__int128)cnt * sumv;
        }

        __int128 diff = total - s;
        if (diff < 0) {
            diff = -diff;
        }

        if (ans == -1 || diff < ans) {
            ans = diff;
        }
    }

    print_int128(ans);

    return 0;
}

brute.cpp 直接枚举所有可能的 W，再按定义把每个区间的检验值都算出来。

这个方法只适合小数据。真正的数据范围里，必须抓住 W 的单调性。

第一步：观察 y(W) 的变化

随着 W 变大，满足：

w_j >= W

的矿石只会变少，不会变多。

所以：

每个区间里的“计数”不会增大
每个区间里的“价值和”也不会增大
区间检验值 count * sum 不会增大

因此总检验值 y(W) 随 W 单调不增。

第二步：怎么快速算一次 y(W)？

固定一个 W 后，我们把每个位置变成两个数组：

a_i = [w_i >= W]
b_i = [w_i >= W] * v_i

然后做两组前缀和：

cnt_prefix
sum_prefix

这样对于任意区间 [l,r]：

满足条件的矿石个数就是 cnt_prefix[r] - cnt_prefix[l-1]
这些矿石价值和就是 sum_prefix[r] - sum_prefix[l-1]

区间贡献就能在 $O(1)$ 算出。
整次 y(W) 的计算复杂度就是 $O(n+m)$ 。

第三步：二分最接近 s 的位置

因为 y(W) 单调不增，所以可以二分找到：

第一个满足 y(W) <= s 的 W

设这个位置是 pos。

那么最优答案只可能出现在：

W = pos
W = pos - 1

原因是：

pos 是第一处掉到 s 以下或等于 s 的地方
pos-1 是它前一个位置，也就是最后一个还在 s 上方的地方

单调函数离目标值最近的点，一定就在这个“分界点”附近。

所以最后只要再算这两个位置的差值，取较小者即可。

Python 知识

zip(weight, value) 把同一矿石的两个属性并行遍历，enumerate(..., 1) 同时得到一基下标。
sum(贡献 for l, r in queries) 用生成器聚合所有区间贡献，参见 /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md。
Python 整数自动支持超过 64 位的中间结果，但本题仍应使用缓冲输入避免 I/O 成为瓶颈。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, target = next(data), next(data), next(data)
weight = [0] * n
value = [0] * n
for i in range(n):
    weight[i], value[i] = next(data), next(data)
queries = [(next(data), next(data)) for _ in range(m)]


def evaluate(limit):
    count = [0] * (n + 1)
    total = [0] * (n + 1)
    c = s = 0
    for i, (w, v) in enumerate(zip(weight, value), 1):
        if w >= limit:
            c += 1
            s += v
        count[i] = c
        total[i] = s
    return sum(
        (count[r] - count[l - 1]) * (total[r] - total[l - 1])
        for l, r in queries
    )


left, right = 0, max(weight) + 2
while left < right:
    middle = (left + right) // 2
    if evaluate(middle) > target:
        left = middle + 1
    else:
        right = middle

print(min(abs(evaluate(limit) - target) for limit in {left, max(0, left - 1)}))

复杂度

时间复杂度： $O((n+m)\log V)$
空间复杂度： $O(n)$

其中 V 是重量的取值范围，本题里最多二分到 max(w_i)+1。

总结

这题的关键是两步：

发现 y(W) 对 W 单调不增
固定 W 时，用两组前缀和快速算出所有区间贡献

一旦把这两步接上，题目就是一个标准的“二分答案 + 前缀和统计”模型。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。