这题各个神仙都用了 \(O(n)\) 的算法，只有我用了 \(O(2^n)\) 的暴搜。
分析
既然要使极差最大，很容易想到要使最大数尽可能大，最小数尽可能地小。那么每一次操作就有两种选择：处理最大数或最小数。在本题中操作次数 \(m \le 10\)，因此可以每次分两种情况，并分别搜索下去。对于每次操作，判断哪种运算能使结果最小或最大，赋值即可。
时间复杂度 \(O(n+2^m)\)，代码如下：
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n,m,a,ma,mi,ans,x,y,cnt;
void dfs(int k,int x)
{
cnt++;
int xx=ma,yy=mi,xxx,yyy;
if(k==1) ma=max(ma+2,max(ma*2,ma/2));
if(k==0) mi=min(mi-2,min(mi/2,mi*2));
xxx=ma,yyy=mi;
ans=max(ans,abs(ma-mi));
if(x>=m) return;
dfs(k,x+1);
ma=xxx,mi=yyy;
dfs(1-k,x+1);
ma=xx,mi=yy;
}
template<typename ty=int>
inline ty read()
{
ty n=0;char c=getchar();bool fl=0;
while(c<33&&c!='-') c=getchar();
if(c=='-') fl=1,c=getchar();
while(c>='0'&&c<='9')
{
n=n*10+(c^48);
c=getchar();
}
return fl?-n:n;
}
template<typename ty>
void pr(ty x)
{
if(!x) return ;
pr(x/10);
putchar(x%10^48);
}
template<typename ty>
inline void write(ty x)
{
if(x==0) putchar('0');
else if(x<0) putchar('-'),x=-x;
pr(x);
}
main()
{
n=read(),m=read();
a=read();
ma=a;
mi=a;
for(int i=2;i<=n;i++)
{
cin>>a;
if(a>ma) ma=a;
if(a<mi) mi=a;
}
x=ma;
y=mi;
dfs(1,1);
ma=x;
mi=y;
dfs(0,1);
write(ans);
return 0;
}