一道二分答案加前缀和###
题目中已经暗示的很明显了 “尽可能靠近” “ 最小值”
本题的主要坑点在于 long long 的使用
abs函数不支持long long !!!
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN=200005;
long long read(){
long long rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
int n,m,w[MAXN],v[MAXN],L[MAXN],R[MAXN];
long long S,T,num[MAXN],pre[MAXN],ans=1000000000000005;
void chk(int x){
T=0;
memset(num,0,sizeof(num));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++){
if(w[i]>=x){
num[i]=num[i-1]+1;
pre[i]=pre[i-1]+v[i];
}else {
num[i]=num[i-1];
pre[i]=pre[i-1];
}
}
for(int i=1;i<=m;i++){
T+=(num[R[i]]-num[L[i]-1])*(pre[R[i]]-pre[L[i]-1]);
}
if(T>=S) ans=min(ans,T-S);
else ans=min(ans,S-T);
//注意最小值不一定在最后产生，而且最小值有可能会很大，一定要初始化一个很大的值
}
int main(){
freopen("in.txt","r",stdin);
n=read();m=read();cin>>S;
int l=100000007,r=0,mid=0;
for(int i=1;i<=n;i++){
w[i]=read();v[i]=read();
l=min(l,w[i]);
r=max(r,w[i]);
}
for(int i=1;i<=m;i++){
L[i]=read();R[i]=read();
}
while(l<=r){
mid=(l+r)>>1;
chk(mid);
if(T==S) break;
if(T>S){
l=mid+1;
}else r=mid-1;
}
cout<<ans;
fclose(stdin);
return 0;
}
