环形纸牌均分问题 贪心

本题是一道非常经典的贪心问题。

1. 我们可以规定方向，进行单向传递，可以传递负数张纸牌，即为逆向抽取。
2. 规定每个人向左传递张纸牌。表示第个人向第个人传递的纸牌数量。
3. 最终每个人手中的纸牌数量是
4. 题目所求是指的可能的最小值。
5. 
6. 问题转化成「货仓选址问题」：给定数轴上的n个点，找出一个到它们的距离之和尽量小的点，这个点就是这些数的中位数。

#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
long long a[1000010], c[1000010];
int main() {
    long long n, ans = 0, ave = 0;
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        ave += a[i];
    }
    ave /= n;
    for (int i = 0; i < n; i++) a[i] -= ave;
    for (int i = 1; i <= n; i++) c[i] = c[i - 1] - a[i - 1];
    nth_element(c + 1, c + (n + 1) / 2, c + n + 1);  // sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++) ans += abs(c[i] - c[(n + 1) / 2]);
    printf("%lld", ans);
    return 0;
}