自动搬运

查看原文

来自洛谷，原作者为

	BqtMtsZDnlpsT **

搬运于2025-08-24 22:14:56，当前版本为作者最后更新于2021-07-14 21:27:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门P5847

思维题。

首先我们考虑，知道了 $S_1$ 就能根据 $M_1$ 推出 $S_2$ 的值，知道了 $S_2$ 就能根据 $M_2$ 推出 $S_3$ 的值，以此类推，所以，知道一个符合范围的 $S_1$，就能求出一个解，具体如下。

$(S_1+S_2)\div 2=M_1\longrightarrow S_2=2\times M_1-S_1$

$(S_2+S_3)\div 2=M_2\longrightarrow S_3=2\times M_2-S_2$

$(S_3+S_4)\div 2=M_1\longrightarrow S_4=2\times M_3-S_3$

$...$

$(S_i+S_{i+1})\div 2=M_1\longrightarrow S_{i+1}=2\times M_{i}-S_{i}$

把 $S_2,S_3...S_{n+1}$ 分别用 $S_1$ 表示得：

$S_2=2\times M_1-S_1$

$S_3=2\times M_2-2\times M_1+S_1$

$S_4=2\times M_3-2\times M_2+2\times M_1-S_1$

$...$

$S_i=\left\{\begin{matrix} 2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot+M_{i-1})-S_1 & (i \bmod 2=0)\\ 2\times(-M_1+M_2-M_3+\cdot\cdot\cdot+M_{i-1})+S_1 & (i \bmod 2=1) \end{matrix}\right.$

即 $S_i=\left\{\begin{matrix} 2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot+M_{i-1})-S_1 & (i \bmod 2=0)\\ -2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot-M_{i-1})+S_1 & (i \bmod 2=1) \end{matrix}\right.$

此时，在题目中我们发现一个还没用过的东西：$S_i\le S_{i+1}$。

于是我们考虑对于每个 $i(1\le i\le n)$ 把 $S_i$、$S_{i+1}$ 带入不等式。

$S_1\le S_2 \longrightarrow S_1\le2\times M_1-S_1 \longrightarrow S_1\le M_1$

$S_2\le S_3 \longrightarrow 2\times M_1-S_1 \le 2\times(M_2- M_1)+S_1 \longrightarrow 2\times(2\times M_1-M_2)\le 2\times S_1 \longrightarrow 2\times M_1-M_2\le S_1$

就像这样，我们可以得到式子：

$S_{i}\le S_{i+1} \longrightarrow \left\{\begin{matrix} S_1\ge 2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot+M_{i-1})-M_{i} & (i \bmod 2=0)\\ S_1\le 2\times (M_1-M_2+M_3-M_4+\cdot\cdot\cdot-M_{i-1})+M_i& (i \bmod 2=1) \end{matrix}\right.$

然后就可以根据每个 $i$ 的不等式得到一个关于 $S_1$ 不等式组，解出这个不等式组即为 $S_1$ 的取值范围，得到 $S_1$ 的取值范围后，因为确定 $S_1$ 即可确定一组解，所以 $S_1$ 的取值范围中整数个数即为所求。

对于这个不等式组，我们发现可以前缀和处理，然后对于奇数的 $i$ 更新答案区间右端点，对于偶数的 $i$ 更新答案区间左端点，设左端点为 $l$，右端点为 $r$，答案即为 $r-l+1$，但是考虑不等式组无解，不能输出负数，应输出 0。

代码（很短）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
int n,l,r,s[5000005],m[5000005];
signed main()
{
	scanf("%lld",&n);
	l=-9223372036854775807,r=9223372036854775807;
	for(int i=1;i<=n;i++)scanf("%lld",&m[i]);
	for(int i=1;i<=n;i++){//前缀和 
		if(i&1)s[i]=s[i-1]+m[i];
		else s[i]=s[i-1]-m[i];
	}
	for(int i=1;i<=n;i++){//求左、右端点 
		if(i&1)r=min(r,(s[i-1]<<1ll)+m[i]);
		else l=max(l,(s[i-1]<<1ll)-m[i]);
	}
	printf("%lld",max(r-l+1,0ll));
	return 0;
}