Codeforces Round #840 (Div. 2) C

这一道题也是我没想到的

题目大意是这样的：可以选择i,j(i<j),我们可以把i到j包括i,j的元素换成abs(a[i],a[j]) ,并且我们需要的答案就是经过一系列这样的操作，使得这个数组的和最大，并输出这一个最大值

我先前一直在想最大值和最小值的差，这样就会让这个差值最大，但是这样还要考虑这样改变划算吗，其他的地方呢？

其实不用这么复杂。

我们可以先考虑n>4的情况

我们第一步可以让a[1],a[2]变成abs(a[1]-a[2]),这样a[1]==a[2],在让a[1]=a[2]=abs(a[1]-a[2]) =0；

下一步就是按这样的方式把a[n]和a[n-1]变成了0

最后一步就是把从1到n的都变成这个数组原来的最大的那个mx，因为abs(mx-0)=mx，这也就是我为什么一定要n>4

如果mx在第1个位置上，那就更好办了，只要把a[n]和a[n-1]变成0了就可以了，mx在最后一个位置也是同样的道理。

如果n==3，那么有以下几种改变方法

1.a[1]和a[2]变成abs(a[1]-a[2])，ans=abs(a[1]-a[2])*2+a[3]

2.a[2]和a[3]变成abs(a[3]-a[2])，ans=abs(a[3]-a[2])*2+a[1]

3.a[1]和a[2]变成0，a[1]=a[2]=a[3] ,ans=a[3]*3

4.a[2]和a[3]变成0，a[2]=a[3]=a[1], ans=a[1]*3

5.先把a[1]变成abs(a[1]-a[2]) ,然后在把a[2],a[3]都变成0，最后a[1]=a[2]=a[3]=abs(a[1]-a[2])(最开始的a[1],a[2]),

ans=abs(a[1]-a[2])*3

6.先把a[3]变成abs(a[3]-a[2]) ,然后在把a[2],a[1]都变成0，最后a[1]=a[2]=a[3]=abs(a[3]-a[2])(最开始的a[3],a[2]),

ans=abs(a[3]-a[2])*3

最后两种可能比较难想到，反正我是没想到

如果n==2

ans=max(a[1]+a[2],abs(a[1]-a[2])*2)//直接判断
后来知道了它获得最大和的方式，就觉得很妙，我在vp的时候真是没什么思路

#include <iostream>
#include <stdlib.h>
#include <cmath>
using namespace std;
const int maxn=2e5+10;
#define int long long 
int n,t;
int a[maxn];
void solve()
{
    cin>>n;
    int mx=-1;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    if (n>3)
    {
        cout<<mx*n<<'\n';
    }
    else if (n==2)
    {
        cout<<max(a[1]+a[2],abs(a[1]-a[2])*2)<<'\n';
    }
    else 
    {
        int ans=max(a[1],a[3]);
        ans=ans*3;
        ans=max(ans,a[1]+a[2]+a[3]);
        ans=max(ans,abs(a[1]-a[2])*3);
        ans=max(ans,abs(a[3]-a[2])*3);
        ans=max(ans,abs(a[1]-a[2])*2+a[3]);
        ans=max(ans,abs(a[3]-a[2])*2+a[1]);
        cout<<ans<<'\n';
    }
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}