狂丿Kurumi @ 2019-04-15 21:08:13
50分,求大佬帮忙查错
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int w[N],v[N],l[N],r[N];
long long pren[N],prev[N];
long long Y,s,sum;
int n,m,mx=-1,mn=0x3f3f3f3f;
bool check(int W)
{
Y=0,sum=0;
memset(pren,0,sizeof(pren));
memset(prev,0,sizeof(prev));
for(int i=1;i<=n;i++)
{
if(w[i]>=W)pren[i]=pren[i-1]+1,prev[i]=prev[i-1]+v[i];
else pren[i]=pren[i-1],prev[i]=prev[i-1];
}
for(int i=1;i<=m;i++)
{
Y+=(pren[r[i]]-pren[l[i]-1])*(prev[r[i]]-prev[l[i]-1]);
}
sum=llabs(Y-s);
if(Y>s)return 1;
else return 0;;
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
mx=max(mx,w[i]);
mn=min(mn,w[i]);
}
for(int i=1;i<=m;i++)
{
cin>>l[i]>>r[i];
}
int left=mn-1,rigth=mx+2,mid;
long long ans=0x3f3f3f3f;
while(left<rigth)
{
mid=(left+rigth)>>1;
if(check(mid))left=mid+1;
else rigth=mid-1;
if(sum<ans) ans=sum;
}
cout<<ans;
return 0;
}
by nofind @ 2019-04-19 21:40:00
@狂丿Kurumi ans开太小了,你看S的范围