二分+前缀和——洛谷P1314_二分与前缀和

1.公式解读

[...]   括号内内容为真则其值等于1，内容为假则其值等于0 

2.思路

这是一个关于单调性判定的问题，当W不断增大，差值由大变小再变大（实际是从负到0到正，只不过要取绝对值，不影响它的单调性），而目标则是在0的附近找到一个绝对值最小的值，因此是一道二分答案题，但如果只用二分法会超时。我们在计算一个区间的和时，通常是用前缀和的方法来缩减时间，直接模拟是n2，而前缀和优化成2∗n。

3.核心代码

while (l<=r)
{
	y=0,mid=l+(r-l)/2;
	for (i=1;i<=n;i++)
	{
		if (w[i]>=mid)
			a[i]=a[i-1]+1,b[i]=b[i-1]+v[i];
		else
			a[i]=a[i-1],b[i]=b[i-1];
	}
	for (i=1;i<=m;i++)
		y+=(a[ri[i]]-a[le[i]-1])*(b[ri[i]]-b[le[i]-1]);
	d=y-s;
	if (d>0)	
        l=mid+1;
	else
    	r=mid-1;
	ans=min(ans,abs(d));
}

4.代码片段分析

（1）求前缀和

for (i=1;i<=n;i++)
{
	if (w[i]>=mid)
		a[i]=a[i-1]+1,b[i]=b[i-1]+v[i];
	else
		a[i]=a[i-1],b[i]=b[i-1];
}

1）循环条件是 i <= n，你可能会疑惑不应该是公式中在区间内的编号才要计算吗，就像图中这样

但是请注意，上述代码还未进行到公式这一步，而是在进行前缀和，可以理解为在预处理。既然是求前缀和，那自然是要整个数组。

2）在这个while循环中，每一次都是一个不同的W（判断值），因此每一次循环的前缀和数组值都不一样

3）我们需要在脑海中想象一个大小为n的数组，若其下标 i 对应的矿石满足条件，则这个数组中以 i 为下标对应的值为 1 ，否则为 0 。

然后开始前缀和，a数组是前缀和数组，对象是上面的n数组，因为要的是满足条件的个数，所以是加 1 。b数组也是前缀和数组，对象是矿石价值数组，所以是加上矿石价值。

（2）带入公式

for (i=1;i<=m;i++)
	y+=(a[ri[i]]-a[le[i]-1])*(b[ri[i]]-b[le[i]-1]);

1）这里的循环条件是 i <= m，处理每一个区间。

2）( a [ ri [ i ] ] - a [ le [ i ] - 1 ] )   对应区间左右边界（ri [ i ] 是右边界，le [ i ] 是左边界），b [ ri [ i ] ] - b [ le [ i ] - 1 ]   对应矿石价值前缀和。

3）y+=   而不是   y=  ，因为是累加各区间和。

（3）二分答案

while (l<=r)
{
    ...
    ...
    d=y-s;
    if (d>0)	
        l=mid+1;
    else
        r=mid-1;
    ans=min(ans,abs(d));
}

二分答案模版，只是把记录答案的位置移到下面去了。不能提前取绝对值，因为要判断差值正负来调整mid，而是在每一次更新答案的时候取绝对值。

5.细节

long long n,m,s,y,d,ans;
long long w[200010],v[200010],le[200010],ri[200010],a[200010],b[200010];
long long l,r,mid;

三处long long，你可能要问为什么 l ，r ，mid 也要long long。

for (i=1;i<=n;i++)
{
	cin>>w[i]>>v[i];
	l=min(l,w[i]);
	r=max(r,w[i]);
}

在读入数据时要找到最大和最小的矿石重量，而min和max函数要求内部参数一致，不能一个int一个long long，实际上w数组没必要long long ，只是定义数组时和a，b数组定义在了一起，而这两个数组要long long，如果你要分开来定义想换成int也无伤大雅，这里只是想提一点min，max函数内部参数可能出现的问题。

6.完整代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
 
long long n,m,s,y,d,ans;
long long w[200010],v[200010],le[200010],ri[200010],a[200010],b[200010];
 
int main()
{
	int i;
	long long l,r,mid;
	l=1e6,r=0,ans=1e15;
	cin>>n>>m>>s;
	for (i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
		l=min(l,w[i]);
		r=max(r,w[i]);
	}
	for (i=1;i<=m;i++)
		cin>>le[i]>>ri[i];
	while (l<=r)
	{
		y=0,mid=l+(r-l)/2;
		for (i=1;i<=n;i++)
		{
			if (w[i]>=mid)
				a[i]=a[i-1]+1,b[i]=b[i-1]+v[i];
			else
				a[i]=a[i-1],b[i]=b[i-1];
		}
		for (i=1;i<=m;i++)
			y+=(a[ri[i]]-a[le[i]-1])*(b[ri[i]]-b[le[i]-1]);
		d=y-s;
		if (d>0)	
			l=mid+1;
		else	
			r=mid-1;
		ans=min(ans,abs(d));
	}
	cout<<ans;
	return 0;
}