环形均分纸牌问题,找c[]的中位数

公式简记为 c[i] = s[i-1] - (i-1)* avg，其中s[]为前缀和数组，avg为平均数,c[1]=0

子母题105. 七夕祭

自己之前错误的原因是数据爆int，索性全部开LL

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

LL a[N],s[N],c[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];

    for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i];

    LL avg = s[n] / n;

    c[1]=0;
    for(int i=2;i<=n;i++) 
    {
        c[i] = s[i-1] - (i-1) * avg;
    }

    sort(c+1,c+n+1); // 还要sort一遍

    LL res=0;
    for(int i=1;i<=n;i++) res += abs(c[i] - c[(n+1)/2]);

    cout << res << endl;

    return 0;
}