题解 | #[NOIP2011]聪明的质监员#
[NOIP2011]聪明的质监员
https://ac.nowcoder.com/acm/problem/16597
从题中描述可以看出w和检验结果之间有一定关系：w越大检验结果越小，w越小检验结果越大。从而得到w的结果具有一个单调的性质。然后根据这个性质可以考虑二分w的做法。
在二分的过程中，如果Y>S那么w就得增大，如果Y<S那么w就得减小，如果Y==S那么直接退出就可以了。但我们最终的答案是需要取|S-Y|的最小值。
在计算Y的过程中也要注意不能直接暴力模拟，由于w的限制无法在一开始就对价格进行前缀和计算，但在计算Y的函数中w的值是确定的，在这时候可以使用前缀和将时间复杂度降低为：O(N)。
否则会超时。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 200000+10;
ll rock[maxn][2];
ll qujian[maxn][2];
ll n, m, S;
ll jiany(ll mid) {
//构造价格的前缀和
ll price[maxn]={}, num[maxn]={}, y=0;
for (int i=1;i<=n;i++) {
price[i] = price[i-1];
num[i] = num[i-1];
if (rock[i][0]>=mid) {
price[i] += rock[i][1];
num[i] += 1;
}
}
//通过前缀和，遍历区间快速求结果
for (int i=1;i<=m;i++) {
y += (num[qujian[i][1]]-num[qujian[i][0]-1])*(price[qujian[i][1]]-price[qujian[i][0]-1]);
}
return y;
}
int main() {
scanf("%lld %lld %lld", &n, &m, &S);
for (int i=1;i<=n;i++) {
scanf("%lld %lld", &rock[i][0], &rock[i][1]);
}
for (int i=1;i<=m;i++) {
//保存测试的左右区间。
scanf("%lld %lld", &qujian[i][0], &qujian[i][1]);
}
ll l = 0, r = maxn, ans = 1e12;
// cout<<jiany(4)<<endl;
while (l<r) {
ll mid = (l+r)/2;
ll Y = jiany(mid);
// cout<<l<<" "<<r<<endl;
// cout<<"Y="<<Y<<endl;
if (Y>S) {
l = mid+1;
ans = min(ans, abs(S-Y));
}
if (Y<S) {
r = mid;
ans = min(ans, abs(S-Y));
}
if (Y==S) {
cout<<mid<<endl;
return 0;
}
}
cout<<ans;
return 0;
}
查看12道真题和解析