[NOIP2011]聪明的质检员

发布于 2017-08-19  120 次阅读



题目(vijos)
二分W,检验答案。
完毕。
只不过检验的时候用一下前缀和,提高运行效率。
另外,这题要用long long!!!!!!
(我才不会说我被long long卡WA掉了呢!)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
ll n,m,s;
int l[200005],r[200005];
ll w[200005],v[200005];
ll sun[200005],suv[200005];
ll check(int x)
{
	ll tmp=0;
	for (int i=1;i<=n;++i)
	{
		sun[i]=sun[i-1];
		suv[i]=suv[i-1];
		if (w[i]>=x) sun[i]++,suv[i]+=v[i];
	}
	for (int i=1;i<=m;++i)
	{
		tmp=tmp+(sun[r[i]]-sun[l[i]-1])*(suv[r[i]]-suv[l[i]-1]);
	}
	return s-tmp;
}
int main()
{
	scanf(
	ll maxnn=0;
	for (int i=1;i<=n;++i)
	{
		scanf(
		maxnn=max(maxnn,w[i]);
	}
	for (int i=1;i<=m;++i)
		scanf(
	int L=0,R=maxnn+2;
	while (L<R)
	{
		int mid=(L+R+1)>>1;
		if (check(mid)<=0) L=mid;
		else R=mid-1;
	}
	printf(
	return 0;
}