P8480 题解

ikunTLE · 2025-09-14 18:00:05 · 题解

思路

想要使极差最大，不难想到贪心策略：使最大值最大，而且最快的方法是让它一直做乘 2 操作。

为什么要时最大值最大而不是最小值最小？

设最小值和最大值分别为 a_1 和 a_2，则有 a_1\le a_2。

最小值除以 2 的操作极差变化为 \Delta a_1=a_1-\lfloor\frac{a_1}{2}\rfloor，而最大值乘 2 的操作极值变化为 \Delta a_2=2a_2-a_2=a_2。

由于 \Delta a_1\le a_1，且 a_1\le a_2，所以 \Delta a_1\le\Delta a_2，所以一定要使最大值最大。

但是还有可能最小值减 2 操作比除以 2 更优，但是不难想到所有的最小值减 2 都可以转化为最大值加 2。

综上所述，首先要求出序列中的最小值和最大值，仅对最大值 a_2 进行操作。若 a_2<2，优先消耗一次次数进行加 2 操作。然后用剩下的次数一直做乘 2 操作。最后算最大值减最小值 a_2-a_1 即可。

注意事项

• 不开 long long 见祖宗。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}

signed main(){
    int n=read(),m=read();
    int maxx=0,minn=INT_MAX;
    for(int i=1;i<=n;++i){
        int x=read();
        maxx=max(maxx,x);
        minn=min(minn,x);
    }
    if(maxx<2){
        maxx+=2;
        --m;
    }
    while(m--)
        maxx*=2;
    printf("%lld\n",maxx-minn);
    return 0;
}