环形均分纸牌。

设平均数为\(ave\),\(g[i]=a[i]-ave\),\(s[i]=\sum_{j=1}^ig[i]\)。

设\(s\)的中位数为\(s[k]\)，则答案为\(\sum |s[i]-s[k]|\)

博主太菜，无法给出证明。

#include 
    
     #include 
     
      using namespace std;const int MAXN = 1000010;long long sum, ans, a[MAXN], s[MAXN];int n;int main(){    scanf("%d", &n);    for(int i = 1; i <= n; ++i)       scanf("%lld", &a[i]), sum += a[i];    sum /= n;    for(int i = 1; i <= n; ++i){        a[i] -= sum; s[i] = s[i - 1] + a[i];    }    sort(s + 1, s + n + 1);    for(int i = 1; i <= n; ++i)       ans += abs(s[i] - s[n / 2 + 1]);    printf("%lld\n", ans);    return 0;}