B4220洗牌

· · 题解

B4220洗牌

新人第一次写题解，请包涵不足

对于每一个绝对值作差（例如 |x-y| ）的式子，其绝对值都可以拆开，形成一个数为正，一个数为负的式子，如下：

|x-y|=\begin{cases} +x - y & x > y \\ -x + y & x \le y \end{cases}

那么，当本题中的式子中的绝对值全部拆开后，我们希望较大的数符号为正，较小的数符号为负，这样答案最大。

举个栗子：
有 6 张牌，分别为 1,2,3,4,5,6 。

如果我们这样排列（写上面的表示比相邻的大）：

      4       5       6
  1       2       3

拆开绝对值，式子为

(4-1)+(4-2)+(5-2)+(5-3)+(6-3)

即

(2\times(4+5)+6)-(2\times(2+3)+1)=13

那么，4,5,6 的符号就是正的，1,2,3 的符号是负的。但是，我们注意到，2,3,4,5 在式子中出现了 2 次。显然，有更优情况，即这样排：

      5       6       4
  3       1       2

拆开绝对值，式子为

(5-3)+(5-1)+(6-1)+(6-2)+(4-2)

即

(2\times(5+6)+4)-(2\times(1+2)+3)=17

得到结论：

当 n 为偶数时，设 a_1\le a_2\le ...\le a_n ，最优结果为

(a_{\frac{n}{2}+1}+2\times (a_{\frac{n}{2}+2} + ... +a_n))-(a_\frac{n}{2}+2\times(a_1+...+a_{\frac{n}{2}-1}))

当 n 为奇数时，与偶数时同理，不过有 2 种构型。

举个栗子：
有 5 张牌，分别为 1,2,3,4,5

构型 1：

  3       5       4
      1       2

构型 2：

      4       5
  2       1       3

两种情况取最大值即可。

给出代码 ：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+10;
int n;
int a[MAXN];
long long mid,l,r,i;
//r表示符号取正的数的和，l表示符号取负的数的和
long long ans;

int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);

    sort(a+1,a+n+1);

    if(n%2==1){//奇数情况
        //构型1：
        mid = n/2;
        for(i=1;i<=mid;i++)
            l += a[i]*2;
        r += a[mid+1]+a[mid+2];
        for(i=mid+3;i<=n;i++)
            r += a[i]*2;
        ans = r-l;
        //构型2：
        l=r=0;
        mid = n/2+1;
        l += a[mid]+a[mid-1];
        for(i=1;i<=mid-2;i++)
            l += a[i]*2;
        for(i=mid+1;i<=n;i++)
            r += a[i]*2;
        ans = max(ans,r-l);
        printf("%lld",ans);
    }
    else{ //偶数情况
        mid = n/2;
        for(i=1;i<mid;i++)
            l += a[i]*2;
        l += a[mid];
        r += a[mid+1];
        for(i=mid+2;i<=n;i++)
            r += a[i]*2;
        ans = r-l;
        printf("%lld",ans);
    }

    return 0;
}