题解 P1314 【聪明的质监员】

xiaohuang · 2019-07-19 21:18:25 · 题解

更好的阅读体验

Solution

这道题直接在[0, \max{w[i]}]二分枚举W，对于每一个枚举出来的w，暴力计算每一个区间的检验值和，这里使用前缀和优化。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

typedef long long LL;
const LL INF = 0x7f7f7f7f7f7f7f7f7f7f;//把ans的初始值设大一点，否则会WA很多
const int MAXN = 200005;
int n, m, w[MAXN], v[MAXN], L[MAXN], R[MAXN];
LL S, l, r, mid, ans, sum1[MAXN], sum2[MAXN];//注意开long long
inline bool check(LL x) {
    for (int i = 1; i <= n; i++)
        if (x <= w[i]) {//如果符合要求的化
            sum1[i] = sum1[i - 1] + 1;
            sum2[i] = sum2[i - 1] + v[i];
        } else {
            sum1[i] = sum1[i - 1];
            sum2[i] = sum2[i - 1];
        }
    LL s = 0;
    for (int i = 1; i <= m; i++)
        s += (sum2[R[i]] - sum2[L[i] - 1]) * (sum1[R[i]] - sum1[L[i] - 1]);//暴力计算每一个区间，累加起来
    if (ans > fabs(s - S)) ans = fabs(s - S);//计算与标准值相差的最小值
    if (S > s) return 1; else return 0;
}
int main() {
    scanf("%d%d%lld", &n, &m, &S);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
        if (w[i] > r) r = w[i];//求区间的右边界（取w[i]的最大值）
    }
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &L[i], &R[i]);
    r++;
    l = 0;
    ans = INF;
    while (l < r) {
        mid = l + r >> 1;//二分枚举
        if (check(mid)) r = mid; else l = mid + 1;//如果大于标准值就往降低要求，否则就提高要求
    }
    printf("%lld\n", ans);
    return 0;
}