NOIP2011 day2 第2题 聪明的质监员 解题报告
二分枚举W。
#include
#include
#include
using namespace std;
const long N(200001);
long n,m,maxw(0),w[N],v[N],L[N],R[N];
long long s,ans,sum[N],sumv[N];
long long f(long W)
{
sum[0]=sumv[0]=0;
for (long i=1;i<=n;i++)
w[i]>=W?(sum[i]=sum[i-1]+1,sumv[i]=sumv[i-1]+v[i]):(sum[i]=sum[i-1],sumv[i]=sumv[i-1]);
long long t(0);
for (long i=1;i<=m;i++)
t+=(sum[R[i]]-sum[L[i]-1])*(sumv[R[i]]-sumv[L[i]-1]);
return t;
}
void solve()
{
long low,mid,high;
long long now;
ans=0x7fffffffffffffffll;
for (low=0,high=maxw;low<=high;)
{
mid=(low+high)/2;
now=f(mid);
if (abs(now-s) if (now==s) return;
if (now else low=mid+1;
}
}
int main()
{
ifstream cin("qc.in");
ofstream cout("qc.out");
cin>>n>>m>>s;
for (long i=1;i<=n;i++) { cin>>w[i]>>v[i]; if (w[i]>maxw) maxw=w[i]; }
for (long i=1;i<=m;i++) cin>>L[i]>>R[i];
solve();
cout< return 0;
}

http://www.cppblog.com/powerwater/articles/177090.html