题解 P1314 【聪明的质监员】

tth37 · 2019-08-27 15:49:05 · 题解

本题难度不大，第一眼就能看出需要用二分答案或倍增答案解决。

需要解决的第一个问题是如何根据一个猜测的参数 W ，快速计算出检验结果 Y 。由于只有 w_j \ge W 的矿石才会对检验结果做出贡献，因此我们可以将 w_j < W 的矿石忽略并预处理前缀和，并且回答 M 个询问即可。

接下来应该考虑如何计算猜测值 W 。观察到 Y(W) 是单调不增的，我们可以用倍增求出满足 Y \ge S 的最大 W 值，那么满足 Y<S 的最小 W 值一定为 W+1 。

最终答案即为 \min\{|Y(W)-S|,|Y(W+1)-S|\} 。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M, ans = 1; ll S;
int w[200005], v[200005], l[200005], r[200005]; ll s1[200005], s2[200005];
inline ll Y(int W) {
    for (register int i = 1; i <= N; ++i)
        s1[i] = w[i] >= W ? s1[i - 1] + 1 : s1[i - 1],
        s2[i] = w[i] >= W ? s2[i - 1] + v[i] : s2[i - 1];
    ll ret = 0;
    for (register int i = 1; i <= M; ++i)
        ret += (s1[r[i]] - s1[l[i] - 1]) * (s2[r[i]] - s2[l[i] - 1]);
    return ret;
}
int main() {
    scanf("%d%d%lld", &N, &M, &S);
    for (register int i = 1; i <= N; ++i) scanf("%d%d", &w[i], &v[i]);
    for (register int i = 1; i <= M; ++i) scanf("%d%d", &l[i], &r[i]);
    for (register int i = 17; i >= 0; --i)
        ans += Y(ans + (1 << i)) >= S ? (1 << i) : 0;
    printf("%lld", min(Y(ans) - S, S - Y(ans + 1)));
}