形式化题目

给定长度 $n$ 的两个正整数数列 $w_i$（重量）、$v_i$（价值）、$m$ 个区间 $[L_i, R_i]$ 以及标准值 $S$。

选定参数 $W$ 后，区间 $[L_i, R_i]$ 的检验值为

其中 $[p]$ 是指示函数（$p$ 为真取 $1$，否则取 $0$）：即「区间内 $w_j \geqslant W$ 的矿石块数」乘以「这些矿石的价值和」。总检验值 $y(W) = \sum\limits_{i=1}^{m} y_i$，要求选择 $W$ 使 $|S - y(W)|$ 最小，输出这个最小值。

样例 $n=5,\ m=3,\ S=15$，矿石 $(w, v)$ 依次为 $(1,5),\ (2,5),\ (3,5),\ (4,5),\ (5,5)$，区间为 $[1,5],\ [2,4],\ [3,3]$。取 $W=4$ 时各区间检验值为：

注意检验值是「块数 × 价值和」，不是单纯的价值和：$W=4$ 时 $y = 20 + 5 + 0 = 25$，与 $S=15$ 相差 $10$，即答案。

正解

思路

按定义计算就是：枚举 $W$，对每个区间扫一遍区间内的矿石统计块数与价值和——单次求值 $O(nm)$；而 $W$ 的取值多达 $10^6$ 个（$w_i \leqslant 10^6$），两者相乘完全不可行。瓶颈有两层：单次求值太贵（区间统计），候选 $W$ 太多（一维搜索），各对应一个经典工具。

观察一：$y(W)$ 关于 $W$ 单调不增。 $W$ 变大时，满足 $w_j \geqslant W$ 的矿石只减不增，每个区间的块数、价值和都不增，乘积 $cnt \times sv$ 也不增，$m$ 个区间求和后 $y(W)$ 仍然单调不增。下表列出样例在 $W = 1 \sim 6$ 的取值：

$y$ 从 175 一路降到 0，差值先减后增，最小值 $10$ 出现在 $y$ 越过 $S$ 的分界点两侧（$W=4$ 与 $W=5$）。单调函数上离目标值最近的点必然落在「越过目标」的分界点附近——这就是二分答案的形状，候选 $W$ 不必枚举 $10^6$ 个，只需 $O(\log \max w)$ 次求值。

观察二：单次求值降到 $O(n+m)$。 固定 $W$ 后，把每块矿石变成两个增量：

• $a_j = [w_j \geqslant W]$：该位置对「块数」的贡献；
• $b_j = [w_j \geqslant W] \cdot v_j$：该位置对「价值和」的贡献。

分别做前缀和 $cnt[i] = \sum\limits_{j \leqslant i} a_j$、$sv[i] = \sum\limits_{j \leqslant i} b_j$，则任意区间 $[l, r]$ 的块数是 $cnt[r] - cnt[l-1]$、价值和是 $sv[r] - sv[l-1]$，检验值就是两者相乘。$m$ 个区间用一个生成器 sum 一次收掉。前缀和把「区间查询」的 $O(n)$ 扫描压成两次相减，单次求值从 $O(nm)$ 降到 $O(n+m)$。

观察三：答案只在分界点两侧产生。 定义谓词 $P(W) := (y(W) \leqslant S)$，由单调性它在 $[1, \max w + 1]$ 上单调（一旦为 true 就恒为 true）——取 $W = \max w + 1$ 时没有任何矿石入选，$y = 0 \leqslant S$（题面保证 $S > 0$），谓词必为 true，二分一定找得到分界点。设 $pos$（代码中的 lo）为第一个满足 $P$ 的 $W$，则：

• $W \geqslant pos$ 一侧：$y(W) \leqslant y(pos) \leqslant S$，差值 $S - y(W)$ 随 $y$ 变小而增大，最小在 $W = pos$；
• $W < pos$ 一侧（$pos > 1$ 时）：$y(W) \geqslant y(pos-1) > S$，差值 $y(W) - S$ 随 $W$ 减小而增大，最小在 $W = pos-1$。

所以答案 $= \min\big(|y(pos) - S|,\ |y(pos-1) - S|\big)$，总共求值 $O(\log \max w) + 2$ 次。$pos = 1$ 时候选 $W = 0$，而所有 $w_i \geqslant 1$，$y(0) = y(1)$，仍然安全。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Ore { ll w, v; };
struct Query { int l, r; };
vector<Ore> ores; vector<Query> qs; ll target; int n, m;
ll evaluate_value(ll limit) {
    vector<ll> cnt(n + 1), sv(n + 1);
    for (int i = 1; i <= n; i++) {
        cnt[i] = cnt[i - 1] + (ores[i - 1].w >= limit);
        sv[i] = sv[i - 1] + (ores[i - 1].w >= limit ? ores[i - 1].v : 0);
    }
    ll total = 0;
    for (int i = 0; i < m; i++) total += (cnt[qs[i].r] - cnt[qs[i].l - 1]) * (sv[qs[i].r] - sv[qs[i].l - 1]);
    return total;
}
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); if(!(cin>>n>>m>>target)) return 0; ores.resize(n); qs.resize(m); ll mx=0; for(int i=0;i<n;i++){cin>>ores[i].w>>ores[i].v; mx=max(mx,ores[i].w);} for(int i=0;i<m;i++) cin>>qs[i].l>>qs[i].r; ll lo=1,hi=mx+2; while(lo<hi){ll mid=(lo+hi)/2; if(evaluate_value(mid)>target) lo=mid+1; else hi=mid;} ll a=evaluate_value(lo), b=evaluate_value(lo-1); cout << min(llabs(a-target), llabs(b-target)) << '\n'; return 0; }

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:32
# update_at: 2026-10-02 09:32

import sys
from collections.abc import Iterator
from itertools import accumulate


def read_ints() -> Iterator[int]:
    """逐行产出输入里的全部整数，避免一次性物化整份输入。"""
    for line in sys.stdin.buffer:
        yield from map(int, line.split())


def evaluate(limit: int, ores: list[tuple[int, int]], queries: list[tuple[int, int]]) -> int:
    """给定阈值 W = limit，用两组前缀和 O(n+m) 算出总检验值 y(W)。

    区间检验值 = 区间内 w >= W 的矿石块数 × 这些矿石的价值和，
    两组前缀和相减即得区间内的块数与价值和。
    """
    cnt = [0] + list(accumulate(w >= limit for w, _ in ores))                # 入选块数前缀和
    sv = [0] + list(accumulate(v if w >= limit else 0 for w, v in ores))     # 入选价值和前缀和
    return sum((cnt[r] - cnt[l - 1]) * (sv[r] - sv[l - 1]) for l, r in queries)


def min_gap(ores: list[tuple[int, int]], queries: list[tuple[int, int]], target: int) -> int:
    """二分第一个 y(W) <= target 的 W（分界点），答案只可能在它与前一个 W 取到。

    W 变大时入选矿石只减不增，y(W) 单调不增；越过 target 之后差值只会更大。
    """
    max_w = max(w for w, _ in ores)
    lo, hi = 1, max_w + 2   # hi 处已无矿石入选，y = 0 <= target，保证二分有分界点
    while lo < hi:
        mid = (lo + hi) // 2
        if evaluate(mid, ores, queries) > target:
            lo = mid + 1    # y 还太高，往右找
        else:
            hi = mid
    return min(abs(evaluate(w, ores, queries) - target) for w in (lo, lo - 1))


def solve() -> None:
    data = iter(read_ints())
    n, m, target = next(data), next(data), next(data)

    ores = [(next(data), next(data)) for _ in range(n)]      # (w_i, v_i)
    queries = [(next(data), next(data)) for _ in range(m)]   # [L_i, R_i]

    print(min_gap(ores, queries, target))


if __name__ == "__main__":
    solve()

复杂度

• 时间 $O((n + m) \log \max w)$：每次 evaluate 两组前缀和扫 $n$ 块矿石、生成器求和扫 $m$ 个区间共 $O(n+m)$；二分区间 $[1, \max w + 1]$，$\max w \leqslant 10^6$ 时至多 $\lceil \log_2(10^6) \rceil = 20$ 轮二分求值，另加最后 2 次候选求值。与 C++ 正解（前缀和 + 二分答案）同阶。
• 空间 $O(n + m)$：矿石与区间各一个列表，evaluate 内两组长度 $n+1$ 的前缀和数组随返回释放。输入用逐行生成器读入，不物化整份 token；实测最大用例峰值约 82MB（Python 对象开销），32MB 限制下有 MLE 风险——C++ 落地时前缀和改用两个 long long 数组，即可压回紧凑的 $O(n+m)$ 内存。

总结

• 检验值定义为「区间内入选矿石的块数 × 价值和」，总检验值 $y(W)$ 关于阈值 $W$ 单调不增——这是全题唯一的性质支点。
• 单调性带来两件事：单次求值用前缀和压到 $O(n+m)$，而「最接近 $S$ 的 $W$」用二分答案压到 $O(\log \max w)$ 次求值。
• 越过分界点 $pos$ 后，无论 $W$ 再怎么取，差值只会更大，因此答案只需在 $pos$ 与 $pos-1$ 两个点里取较小者。
• 整体 $O((n + m) \log \max w)$，与标准 C++ 正解同阶；Python 实现 20 组真实数据全部通过。