TIOJ 1799 . Richmen

環狀分錢問題，有點好奇推廣

0. 水母？
1. 仙人掌？
2. 2D？
3. 平面圖？
3. 一般圖？

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long int int64;

int64 arr[5000010];

int main(){
    int64 n; scanf("%lld", &n);
    int64 avg = 0;
    arr[0] = 0;
    for(int lx = 1;lx <= n;lx++){
        scanf("%lld", arr+lx);
        avg += arr[lx];
        arr[lx] += arr[lx-1];
    }
    avg /= n;
    for(int lx = 1;lx < n;lx++)
        arr[lx] -= lx*avg;

    sort(arr, arr+n);
   
    n--;  
    for(int lx = n;lx >= 1;lx--)
        arr[lx] = arr[lx]-arr[lx-1];
   
    int64 ans = 0;
    for(int lx = 1;lx <= n;lx++){
        if(lx <= n/2) ans += lx*arr[lx];
        else ans += (n-lx+1)*arr[lx];
    }

    printf("%lld\n", ans);
    return 0;
}