哈娜 @ 2019-08-24 15:28:55
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct ore{
int w,v;
}a[200001];
int n,m,r1=-1,l1=2147483647;
long long s,ans,y;
int l[200001],r[200001],pre[200001],va[200001];
int work(int mid)
{
y=0;
memset(pre,0,sizeof(pre));//记录前i个矿石中大于W的个数
memset(va,0,sizeof(va)); // 大于W的矿石总价值
for(int i=1;i<=n;++i)
if(a[i].w>=mid) {pre[i]=pre[i-1]+1;va[i]=va[i-1]+a[i].v;}
else {pre[i]=pre[i-1];va[i]=va[i-1];} //前缀和处理数据节约空间
for(int i=1;i<=m;++i)
y+=(pre[r[i]]-pre[l[i]-1])*(va[r[i]]-va[l[i]-1]);
}
int main()
{
cin>>n>>m>>s; //矿石个数 区间个数 比较值
for(int i=1;i<=n;++i)
{
cin>>a[i].w>>a[i].v; //重量 价值
if(a[i].w>r1) r1=a[i].w;
if(a[i].w<l1) l1=a[i].w;
}
for(int i=1;i<=m;++i)
cin>>l[i]>>r[i]; //区间端点
l1=l1-1;r1=r1+1; //避免左右端点符合题意的情况
ans=0x3f3f3f3f3f3f3f3f;
while(l1<=r1)
{
int mid=(r1+l1)/2;
work(mid);
if(y>s) l1=mid+1;
if(y==s) {cout<<0;return 0;}
if(y<s) r1=mid-1;
y=llabs(y-s); //int型用abs long long用llabs
ans=min(ans,y);//寻找最小的值
}
cout<<ans;
return 0;
}
by 萧萧尹 @ 2019-10-03 13:47:03
和你错的一样 我也很迷
by hszsfzlxj @ 2019-11-05 17:32:39
前缀和数组要开long long