自动搬运

查看原文

来自洛谷，原作者为

	Rs_LightRay **

搬运于2025-08-24 21:17:56，当前版本为作者最后更新于2025-04-23 21:27:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}