环形均分纸牌问题

$$ 有n个小朋友坐成一圈，每人有a[i]个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 $$

求解:

$$ 设 p[i] 表示 i给 (i + 1 ){p[i]}个糖果, 所以如果p[i] 为负数, 则表示 i + 1给 (i) |p[i]|个糖果 $$

$$ 单独的， 设 p[n] 表示 n 给 (1) p[n] 个糖果 $$

那么对于我答案就是
$$ ans = \sum_{i = 1} ^ {n}{|p[i]|} $$
观察这个式子， 考虑用p[1] 来替代所有的 p[i]
$$ p[2] = p[1] + a[2] - avg $$

$$ p[3] = p[2] + a[3] - avg = p[1] + (a[2] - avg) + (a[3] - avg) $$

$$ p[4] = p[3] + a[4] - avg = p[1] + (a[2] - avg) + (a[3] - avg) + (a[4] - avg) $$

由上述式子发现
$$ p[i] = \sum_{j = 2}^{i}{(a[j] - avg)} + p[1] $$
如果一开始就令所有的 a[i] 减去 avg 则可以变成
$$ p[i] = \sum_{j = 2}^{i}{a[j]} + p[1] $$
那么答案就是
$$ ans = |p[1]| + \sum_{i = 2}^{n} {|\sum_{j = 2}^{i}{a[j]} + p[1]|} $$
令
$$ c[i] =\sum_{j = 2}^{i}{a[j]} $$
则有
$$ ans = |p[1]| + \sum_{i = 2}^{n} {|c[i] + p[1]|} $$
可以令 c[1] = 0

则原式子可以变成
$$ ans = \sum_{i = 1}^{n} {|c[i] + p[1]|} $$
转换一下
$$ ans = \sum_{i = 1}^{n} {|c[i] - ( -p[1])|} = \sum_{i = 1}^{n} {|c[i] - z|} (令 z = (-p[i])) $$
那么此时我们发现， 因为我们只是要求的ans, 而绝对值里面的项本质就是在一个线段上， 选择一个点(z)， 到所有的 c[i] 的距离最小, 然后取总和, 那么就是取中间的数

而对于本题的 行和列分开考虑互不影响，基本上不需要解释， 所以答案就是两个方向上各求一边即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn], b[maxn];
int n, m, k;
ll c[maxn];
ll get(int *a, int n) {
    ll ans = 0;
    for (int i = 1; i <= n; ++i) ans += a[i];
    ans /= n;
    for (int i = 1; i <= n; ++i) a[i] -= ans;
    c[1] = 0;
    for (int i = 2; i <= n; ++i) c[i] = c[i - 1] + a[i];
    sort(c + 1, c + n + 1);
    int mid = c[n / 2 + 1];
    ll sum = 0;
    for (int i = 1; i <= n; ++i) sum += abs(c[i] - mid);
    return sum;
}
int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++i) {
        int l, r; 
        scanf("%d%d", &l, &r);
        a[l]++, b[r]++;
    }
    if (k % n && k % m) {
        puts("impossible");
    }  else if (k % n) {
        printf("column %lld", get(b, m));
    } else if (k % m) {
        printf("row %lld", get(a, n));
    } else {
        printf("both %lld", get(a, n) + get(b, m));
    }
     return 0;
}