原题

题目链接

思路

有两种思考方式：

通过均分纸牌问题迁移

均分纸牌问题是本题的一个简化版，非环情况。对于非环情况，容易发现，最值就是$\sum{i=1}^{M}|i\times avg-G[i]|$，其中$avg$是所有数的均值（下同），$G[i]$是前缀和。为了简化问题，我们将原先的前缀和$G[i]$预处理为$S[i]=G[i]-i\times avg$（也就是每一个数字减去均值），那么最小值就是$\sum{i=1}^{M}|S[i]|$。

对于环形情况，一个自然的想法是通过断开环来构造一个最值情况。问题变成是否存在两个点，他们之间没有发生纸牌的传递，这里的证明我没有想清楚，但是可以猜测，必然存在一组最优解满足该约束。那么，我们便可以将环从这样的两个点之间断开，从而原问题变成了一个均分纸牌问题。

当我们从$k$处断开环时，断开之后的环如下（其中$A[i]$是原先的数字减去$avg$之后的值）：

IMG_0214

显然，$S[M]=0$，故而所求的最值就是$\sum_{i=1}^{M}|S[i]-S[k]|$，显然最值当$S[k]$为中位数时取得。

解方程组

该题解来自于csdn:

image-20210203205950654

代码

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
typedef long long ll;
ll sum[N];

int main(){
    memset(sum,0,sizeof(sum));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    
    ll ave = sum[n]/n;
    for(int i = 1;i<=n;i++){
        sum[i]-=i*ave;
    }
    
    nth_element(sum+1, sum+1+n/2, sum+n+1);
    ll res =0;
    ll mid = sum[1+n/2];
    for(int i=1;i<=n;i++){
        res += abs(mid-sum[i]);
    }
    cout<<res<<endl;
    return 0;
}