题解 P1314 聪明的质检员

lew2018 · 2019-07-30 21:12:37 · 题解

主要思路就是二分参数W的值，在二分的过程中可以使用前缀和来O(1)地求出\sum^{m}_{i = 1}Y_i的值。这样每次二分的复杂度就是O(n+m)。
再来考虑二分边界的问题，很显然左边界应该是0，即每个石头都选，而右边界则应该是1e6 + 1，这样就可以考虑到一个石头都不选的情况。
具体实现的时候还有一些细节，比如前缀和数组开long\ long，二分时应该写成mid=(l+r+1)\div 2 否则会有死循环。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 200006;
ll S, sum[N];
int w[N], v[N];
int cnt[N], L[N], R[N], n, m; 

ll check(int W) {
    for (int i = 1; i <= n; i++) {
        if (w[i] >= W) {  //求前缀和数组的过程
            sum[i] = sum[i - 1] + v[i];
            cnt[i] = cnt[i - 1] + 1;
        } else {
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }
    }
    ll res = 0;
    for (int i = 0; i < m; i++) {
        res += (sum[R[i]] - sum[L[i] - 1]) * (cnt[R[i]] - cnt[L[i] - 1]);
    }
    return res;
}

int main() {
    cin >> n >> m >> S;
    for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
    for (int i = 0; i < m; i++) scanf("%d%d", &L[i], &R[i]);
    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;  //因为更新时是l = mid，所以应该写成mid = (l + r + 1) >> 1
        if (check(mid) >= S) l = mid;
        else r = mid - 1;
    }
    cout << min(abs(check(r) - S), abs(S - check(r + 1))) << endl;
    return 0;
}