二分枚举W。
#include<fstream>
#include<algorithm>
#include<cmath>
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)<ans) ans=abs(now-s);
if (now==s) return;
if (now<s) high=mid-1;
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<<ans<<endl;
return 0;
}
posted on 2012-06-01 16:51
龙在江湖 阅读(412)
评论(0) 编辑 收藏 引用 所属分类:
竞赛题解_NOIP