看懂题目最重要
注意数据范围

思路

1. 区间检验值$Y_i$ = 该区间所有重量大于$W$的矿石总个数 * 这些矿石的总价值
   • 区间有多个，为避免反复求个数和总和，优化为前缀和求部分和
2. 检验结果 = 各区间检验值之和，$Y = \sum Y_i$
   • 对于不同的$W$，所得$Y_i$不同，最终的检验结果$Y$也不同
   • 但是$W$越大，满足条件的矿石个数就越少，总价值也越少，所以$Y_i$越小，最终的检验结果$Y$也就越小
   • 此时，必有一个$W$使得$Y \leq S$，且$(W-1)$使得$Y’ > S$，而这两个取值就是检验结果最靠近标准值$S$的点
3. 直接枚举$W$比较困难，而$W$与$Y$存在单调性，考虑二分

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, m, N = 200010;
    static long S;
    static int[] w = new int[N], v = new int[N], L = new int[N], R = new int[N], cnt = new int[N];
    static long[] sum = new long[N];

    static long getY(int W) {
        for (int i = 1; i <= n; i++) {  // 计算满足 wi>=w 的前缀个数和价值前缀和
            cnt[i] = cnt[i - 1];
            sum[i] = sum[i - 1];
            if (w[i] >= W) {
                cnt[i]++;
                sum[i] += v[i];
            }
        }
        long res = 0;  // 检验结果Y 注意数据范围long 别漏掉了
        for (int i = 1; i <= m; i++)
            res += (cnt[R[i]] - cnt[L[i] - 1]) * (sum[R[i]] - sum[L[i] - 1]);  // 从前缀和计算部分和
        return res;
    }

    public static void main(String[] args) {
        n = scanner.nextInt();
        m = scanner.nextInt();
        S = scanner.nextLong();
        for (int i = 1; i <= n; i++) {  // 存重量和价值
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        for (int i = 1; i <= m; i++) {  // 存各区间左右界
            L[i] = scanner.nextInt();
            R[i] = scanner.nextInt();
        }
        int l = 0, r = (int) 1e6 + 1;  // 右界超出范围 是考虑到可能一个矿石都不选的情况
        while (l < r) {  // 二分查找  求“检验结果小于S”的W最大值
            int mid = l + r >> 1;
            if (getY(mid) <= S) r = mid;  // W越大Y越小 Y<=S时搜左半区间
            else l = mid + 1;
        }
        System.out.println(Math.min(S - getY(r), getY(r - 1) - S));  // 注意要求绝对值或保证结果正数
    }
}