P1314 聪明的质监员

读完题后，我们会发现这道题的题意非常简单，大意就是有n件物品，m个区间，求每个区间检验值之和，通过改变参数使标准值与检验值的差的绝对值最小

很明显，检验值的变动只与参数有关，我们可以二分参数来搜索答案
由题意可知，参数至小为0，至大为所有物品中最大的重量，再大则与至大值意义相同
那么每次用前缀和记录当前参数下的\(\sum_j1\)值和\(\sum_jv_j\)值，来做到\(O(1)\)查询区间
最后在每次二分中修改ans即可

下放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<cmath>
#define ll long long
#define gc() getchar()
#define maxn 200005
using namespace std;

inline ll read(){    //快读
	ll a=0;int f=0;char p=gc();
	while(!isdigit(p)){f|=p=='-';p=gc();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
	return f?-a:a;
}
void write(ll a){    //快写
	if(a>9)write(a/10);
	putchar(a%10+'0');
}

int n,m,st,la,w[maxn],v[maxn],l[maxn],r[maxn];
ll s,sl[maxn],jz[maxn],ans;   //sl数组记录满足参数的数量，jz数组记录满足参数的价值
bool check(ll x){
	ll sum=0;
	for(int i=1;i<=n;++i){
		sl[i]=sl[i-1]+(w[i]>=x?1:0);     //使用前缀和记录满足条件的物品数量
		jz[i]=jz[i-1]+(w[i]>=x?v[i]:0);    //同上记录满足条件的物品价值之和
	}
	for(int i=1;i<=m;++i)
		sum+=(sl[r[i]]-sl[l[i]-1])*(jz[r[i]]-jz[l[i]-1]);   //可以做到对每个区间进行O(1)查询
	if(abs(s-sum)<ans)ans=abs(s-sum);    //每次查找修改答案
	return sum>s;     //若参数越小则检验值越大，反之越小
}

int main(){
	n=read();m=read();s=read();      //s要用long long定义，否则只能拿30分
	for(int i=1;i<=n;++i)w[i]=read(),v[i]=read(),la=max(la,w[i]);
	for(int i=1;i<=m;++i)l[i]=read(),r[i]=read();
	ans=1000000000000000;     //ans赋初值一定要足够大
	while(st<=la){
		int m=st+la>>1;
		if(check(m))
			st=m+1;
		else
			la=m-1;
	}
	write(ans);
	return 0;
}

P1314 聪明的质监员

推荐阅读