洛谷题单指南-前缀和差分与离散化-P1314 [NOIP2011 提高组] 聪明的质监员

原题链接：https://www.luogu.com.cn/problem/P1314

题意解读：计算m个检验值之和，计算与s差值绝对值的最小值。

解题思路：

1、首先要搞懂检验值是如何计算的

如上图，对于每一个区间的检验值yi，表示为：yi = "该区间重量>=W的矿石个数"  ✖️ "该区间>=W的矿石价值之和"

检验值y即所有yi(1<=i<=m)之和。

要快速计算l ~ r区间里>=W的矿石个数，以及l ~ r区间里>=W的矿石价值之和，可以借助前缀和。

2、W和检验值y的关系

W越大，符合>=W的矿石就越少，因此y值会越小，可以看出，W与y之间具有单调性，所以可以采用二分W来求y >= s的最小的y，进而计算|y-s|。

3、完整流程

第一步：二分W的值mid

第二步：针对W，计算前缀和数组sc、sv，sc[i]表示前i个矿石里重量>=W的个数，sv[i]表示前i个矿石里重量>=W的价值之和

第三步：计算检测值y，如果y>=s，往更大范围搜l = mid + 1，否则r = mid - 1

第四步：更新答案，这里要注意是计算|y-s|的最小值

当y>=s时，应该增大W，使得|y-s|更小

当y<s时，应该缩小W，使得|y-s|更小

因此，不管y>=s还是y<s，都应该更新一次答案。

100分代码：

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

const int N = 200005;

int n, m;
long long s, ans = 1e18;
int w[N], v[N], l[N], r[N];
long long sc[N], sv[N];

bool check(int W)
{
    //计算前缀和sc，sv
    //memset(sc, 0, sizeof(sc));
    //memset(sv, 0, sizeof(sv));
    for(int i = 1; i <= n; i++)
    {
        if(w[i] >= W)
        {
            sc[i] = sc[i - 1] + 1;
            sv[i] = sv[i - 1] + v[i];
        } 
        else
        {
            sc[i] = sc[i - 1];
            sv[i] = sv[i - 1];
        } 
    }
    //计算检验值y
    long long y = 0;
    for(int i = 1; i <= m; i++)
    {
        y += (sc[r[i]] - sc[l[i] - 1]) * ((sv[r[i]] - sv[l[i] - 1]));
    }
    //注意不管y>=s还是y<s，都应该更新答案
    ans = min(ans, abs(y - s));
    //判断检验值
    if(y >= s) return true;
    else return false;
}

int main()
{
    cin >> n >> m >> s;
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for(int i = 1; i <= m; i++) cin >> l[i] >> r[i];

    int left = 1, right = 1e9; 
    while(left <= right)
    {
        int mid = left + right >> 1;
        if(check(mid)) left = mid + 1;
        else right = mid - 1;
    }
    cout << ans;
    return 0;
}