PMTD

uuku · 2022-08-15 21:49:18 · 题解

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

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

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

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

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

显然有 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;
}