一道二分答案加前缀和###

题目中已经暗示的很明显了 “尽可能靠近” “ 最小值”

本题的主要坑点在于 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;

}