题解

问题分析

这道题要求通过调整参数 $W$ 的值，使得检验结果 $Y$ 与标准值 $S$ 的绝对差 $|S-Y|$ 最小。

检验结果 $Y$ 的计算方式：对于每个区间 $[L_i,R_i]$，统计满足 $w_j \geq W$ 的矿石数量和价值总和，然后将数量与价值相乘得到该区间的检验值 $Y_i$，最后将所有区间的 $Y_i$ 相加得到 $Y$。

解题思路

1. 关键观察

• 当 $W$ 增大时，满足条件的矿石数量减少，检验值 $Y$ 减小
• 当 $W$ 减小时，满足条件的矿石数量增加，检验值 $Y$ 增大
• 因此 $Y$ 关于 $W$ 是单调递减的

2. 算法设计

利用二分查找在可能的 $W$ 值范围内寻找最优解：

• 二分范围：$l = 0$, $r = \max(w_i)$
• 判断条件：计算当前 $W$ 对应的检验值 $Y$，比较 $Y$ 与 $S$ 的大小关系
• 优化计算：使用前缀和数组快速计算区间内满足条件的矿石数量和价值

3. 代码解析

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, s, l, r;
int mid, ss, ans;
int w[200010], v[200010], le[200010], ri[200010];
int q[200010], p[200010];  // 前缀和数组
int minn = 1e15;  // 记录最小差值

signed main() {
    cin >> n >> m >> s;
    
    // 读入矿石数据，确定W的二分上界
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
        r = max(r, w[i]);
    }
    
    // 读入区间数据
    for (int i = 1; i <= m; i++) {
        cin >> le[i] >> ri[i];
    }
    
    // 二分查找最优W值
    while (l <= r) {
        ans = 0, mid = (l + r) >> 1;  // 当前W值
        
        // 构建前缀和数组
        for (int i = 1; i <= n; i++) {
            if (w[i] > mid) {  // 重量大于当前W
                q[i] = q[i - 1] + 1;        // 数量前缀和
                p[i] = p[i - 1] + v[i];     // 价值前缀和
            } else {
                q[i] = q[i - 1];
                p[i] = p[i - 1];
            }
        }
        
        // 计算所有区间的检验值之和Y
        for (int i = 1; i <= m; i++) {
            ans += (q[ri[i]] - q[le[i] - 1]) * (p[ri[i]] - p[le[i] - 1]);
        }
        
        ss = s - ans;  // 计算差值
        
        // 根据差值调整二分边界
        if (ss < 0) {  // Y > S，需要增大W来减小Y
            l = mid + 1;
        } else {       // Y <= S，需要减小W来增大Y
            r = mid - 1;
        }
        
        minn = min(minn, abs(ss));  // 更新最小差值
    }
    
    cout << minn;
    return 0;
}

算法复杂度

• 时间复杂度：$O((n+m)\log(\max(w_i)))$
  • 二分查找：$O(\log(\max(w_i)))$
  • 每次二分：构建前缀和 $O(n)$，计算检验值 $O(m)$
• 空间复杂度：$O(n+m)$

样例分析

对于样例：

5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3

当 $W=4$ 时：

• 区间 $[1,5]$：满足条件的矿石有2个（重量4,5），检验值 $2 \times (5+5) = 20$
• 区间 $[2,4]$：满足条件的矿石有1个（重量4），检验值 $1 \times 5 = 5$
• 区间 $[3,3]$：没有满足条件的矿石，检验值 $0$
• 总和 $Y=25$，与 $S=15$ 的差值为 $10$

该算法通过二分查找找到了这个最优解。