P1314 [NOIP2011 提高组] 聪明的质监员

题目

[NOIP2011 提高组] 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi 。检验矿产的流程是：

1. 给定m 个区间 [li,ri]；
2. 选出一个参数 W；
3. 对于一个区间 [li,ri]，计算矿石在这个区间上的检验值 yi：
   

其中 j 为矿石编号。

这批矿产的检验结果 y 为各个区间的检验值之和。即：

若这批矿产的检验结果与所给标准值 s 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近标准值 s，即使得 |s-y|最小。请你帮忙求出这个最小值。

输入格式

第一行包含三个整数 n,m,s，分别表示矿石的个数、区间的个数和标准值。

接下来的 n 行，每行两个整数，中间用空格隔开，第 i+1 行表示 i 号矿石的重量 wi 和价值 vi。

接下来的 m 行，表示区间，每行两个整数，中间用空格隔开，第 i+n+1 行表示区间 [li,ri] 的两个端点 li 和 ri。注意：不同区间可能重合或相互重叠。

输出格式

一个整数，表示所求的最小值。

样例 #1

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

输出 #1

10

题解

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>

const int N = 2e5 + 10;
long long n, m, goal;  
int w[N], v[N], l[N], r[N];  // w 为矿石的重量，v 为矿石的价值，l 和 r 为区间的起始和结束位置
long long a[N], s[N];  // a 是存储前缀和的数组，s 是存储前缀和的矿石价值数组

using namespace std;

// 检查给定 W 值时的检验结果
long long check(int mid);

int main() {
    cin >> n >> m >> goal;
    
    // 输入矿石的重量和价值
    for(long long i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    // 输入区间的起始和结束位置
    for(long long i = 0; i < m; i++) {
        cin >> l[i] >> r[i];
    }

    // 二分查找的右边界是 w 的最大值 + 1
    long long l = 0, r = 1e6 + 1;
    
    while(l < r) {
        long long mid = l + r + 1 >> 1;
        if(check(mid) >= goal) {
            l = mid;  // 说明当前 W 值可以满足条件，继续尝试更大的 W
        } else {
            r = mid - 1;  // 如果不能满足目标值，尝试更小的 W
        }
    }

    // 输出最接近目标的结果，检查 l 和 r 对应的检验值差值
    cout << min(abs(check(r) - goal), abs(check(r + 1) - goal)) << endl;
}

// 计算给定 W 值时的检验值
long long check(int mid) {
    long long y = 0;

    // 更新前缀和数组
    for(long long i = 1; i <= n; i++) {
        if(w[i] >= mid) {
            a[i] = a[i - 1] + 1;  // 矿石重量大于等于 W，数量 +1
            s[i] = s[i - 1] + v[i];  // 矿石价值加上
        } else {
            a[i] = a[i - 1];
            s[i] = s[i - 1];
        }
    }

    // 计算所有区间的检验值
    for(long long i = 0; i < m; i++) {
        // 根据前缀和计算每个区间的检验值
        long long count = a[r[i]] - a[l[i] - 1];  // 区间内满足条件的矿石数量
        long long value_sum = s[r[i]] - s[l[i] - 1];  // 区间内满足条件的矿石的价值和
        y += count * value_sum;  // 计算检验值并累加
    }

    return y;
}