自动搬运

查看原文

来自洛谷，原作者为

	uuku **

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

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

以下是正文

设当前的最大值为 $mx$，最小值为 $mn$。为了让极差变大，我们显然是只操作这两个数。并且一定是让 $mx$ 变大，$mn$ 变小。

所以我们只可能进行这四个操作：

1. $mx:=mx+2$。
2. $mx:=mx\times 2$。
3. $mn:=mn-2$。
4. $mn:=\lfloor \dfrac {mn}{2}\rfloor$。

下面我们就来考虑那种操作对答案的贡献更大：

设一次操作对答案的贡献为 $dlt$。

那么这四种操作的贡献分别为：

1. $dlt_1=2$。
2. $dlt_2=mx$。
3. $dlt_3=2$。
4. $dlt_4=mn-\lfloor \dfrac{mn}{2}\rfloor$。

显然有 $dlt_4\le mn \le mx=dlt_2$。所以操作 $4$ 不可能进行。也就意味着如果我们改变最小值，每次操作最多将答案 $+2$。而如果改变最大值，每次操作至少可以让答案 $+2$。所以我们只要操作最大值就可以了。

下面我们考虑如何选取 $1$ 和 $2$ 操作。

不难发现，当 $mx>2$ 时，进行 $2$ 操作更优。当 $mx=2$ 时，两种操作效果一样。当 $mx<2$ 时，进行 $1$ 操作更优。

并且当进行一次 $1$ 操作后必然有 $mx\ge2$。

所以我们只需要记录初始序列的最大值和最小值，如果最大值小于 $2$，就先将其 $+2$，然后不断的对最大值进行 $\times 2$ 操作即可。

下面是 $\text{std}$：

#include<cstdio>
int n,val,mx,mn=1e9,m;
int main()
{
	scanf("%d%d",&n,&m);
	while(n--)
	{
		scanf("%d",&val);
		if(val>mx)mx=val;
		if(val<mn)mn=val;
	}
	if(mx<2)mx+=2,m--;
	printf("%lld",((1ll*mx)<<m)-mn);
	return 0;
}