[NOIp2011] luogu P1314 聪明的质监员

题目描述

点进去看吧，说的不能再清楚了。

Solution

看到数据规模不难想到二分 WWW，然后用个前缀和优化一下即可。注意上下界。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define int long long

const int MAXN=200010;

int n,m,s;

int maxx=-1,minn=0x3f3f3f3f;

int ans=(int)1e17l;

int Y,cnt;

int sumn[MAXN],sumv[MAXN];

int v[MAXN],w[MAXN];

int l[MAXN],r[MAXN];

int check(int x){

	Y=cnt=0;

	memset(sumn,0,sizeof(sumn));

	memset(sumv,0,sizeof(sumv));

	for(int i=1;i<=n;i++)

	{

		if(w[i]>=x) sumn[i]=sumn[i-1]+1,sumv[i]=sumv[i-1]+v[i];

		else sumn[i]=sumn[i-1],sumv[i]=sumv[i-1];

	}

	for(int i=1;i<=m;i++)

		Y+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);

	cnt=abs(Y-s);

	return Y>s;

}

inline int read(){

	int x=0; char c;

	do c=getchar(); while(c<'0'||c>'9');

	while(c>='0'&&c<='9')

		x=x*10+c-48,c=getchar();

	return x;

}

signed main(){

	n=read();m=read();s=read();

	for(int i=1;i<=n;++i){

		w[i]=read();v[i]=read();

		maxx=max(maxx,w[i]);minn=min(minn,w[i]);

	}

	for(int i=1;i<=m;++i){

		l[i]=read();

		r[i]=read();

	}

	int left=minn-1,right=maxx+2,mid;

	while(left<=right){

		mid=(left+right)/2;

		if(check(mid))

			left=mid+1;

		else

			right=mid-1;

		ans=min(ans,cnt);

	}

	printf("%lld",ans);

}

巴特西

[NOIp2011] luogu P1314 聪明的质监员

题目描述

Solution

最新文章

热门文章