题目链接
咕咕咕
本题难度不大，第一眼就能看出需要用二分答案或倍增答案解决。
需要解决的第一个问题是如何根据一个猜测的参数 $W$ ，快速计算出检验结果 $Y$ 。由于只有 $w_j \ge W$ 的矿石才会对检验结果做出贡献，因此我们可以将 $w_j < W$ 的矿石忽略并预处理前缀和，并且回答 $M$ 个询问即可。
接下来应该考虑如何计算猜测值 $W$ 。观察到 $Y(W)$ 是单调不增的，我们可以用倍增求出满足 $Y \ge S$ 的最大 $W$ 值，那么满足 $Y<S$ 的最小 $W$ 值一定为 $W+1$ 。
最终答案即为 $\min\lbrace |Y(W)-S|,|Y(W+1)-S|\rbrace$ 。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #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)));
}
|