https://www.luogu.org/problemnew/show/P1314

两个点：

1.二分答案，因为Y关于W是单调的，W越大，Y越小。

2.有了二分，对于一个确定的W，要高效算出此时的Y，用前缀和，sum(i)和sumv(i)分别表示前i个矿石中>=W的个数及价值和，然后就可以用sum(b)-sum(a-1)以及sumv在O(1)得到一个区间的信息了。与序列多次区间求和是一样的思想。

#include<bits/stdc++.h>
using namespace std;

int n,m,w[1000005],v[1000005],a[1000005],b[1000005];
long long s,ans=(1LL<<60),sum[1000005],sumv[1000005];
bool check(int W)
{
	for(int i=1;i<=n;i++)
	{
		if(w[i]>=W)
		{
			sum[i]=sum[i-1]+1;
			sumv[i]=sumv[i-1]+v[i];
		}
		else sum[i]=sum[i-1],sumv[i]=sumv[i-1];
	}
	long long tot=0;
	for(int i=1;i<=m;i++)
	{
		tot+=(sum[b[i]]-sum[a[i]-1])*(sumv[b[i]]-sumv[a[i]-1]);
	}
	ans=min(ans,abs(tot-s));
	return tot<s?0:1;
}

void binary()
{
	int l=0,r=1000000,mid;
	while(l<=r)
	{
		mid=l+(r-l)/2;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
}

int main()
{
	freopen("input.in","r",stdin);
	scanf("%d%d%lld",&n,&m,&s);
	for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]);
	binary();
	printf("%lld\n",ans);
	return 0;
}

再说一下其他二分答案的一些问题。

洛谷P1083借教室https://www.luogu.org/problemnew/show/P1083

运用了二分答案+差分+前缀和，感觉这个最难想到。这道题的单调性是：只要有一天不符合了，那么它后面的每一天都不符合了。于是二分最多处理多少个订单，假设是m，那么要判断前m个订单是否可以满足，差分+前缀和过一遍就可以了。

P1182 数列分段`Section II`https://www.luogu.org/problemnew/show/P1182                最小化最大值

P1316 丢瓶盖https://www.luogu.org/problemnew/show/P1316                   最大化最小值

 

总体来讲，适合用二分答案求解的题目必须满足：状态的决策过程或者序列满足单调性。

盗一张大佬Mashiro_ylb https://blog.csdn.net/Mashiro_ylb/article/details/78469151 的图：

 

 

 

写二分答案代码使，要注意的几点：目前还处于懵逼状态，日后多刷题再总结吧

1.左右边界能否取到

2.while(l<r)还是(l<=r)

3.check(mid)后更新时l和r中的其中一个等于mid，另一个偏离，还是用一个ans保存mid，l和r都偏离

4.区间剩下两三个数时，会不会丢解

5.区间剩下两三个数时，会不会死循环