https://www.acwing.com/problem/content/107/
很显然行和列是独立的，求出平均值之后变成“一个环，交换最小的次数使得各个位置相等”。假设要交换，则考虑最大的数，它要么把货物传递到左边，要么把货物传递到右边。多出来的部分一直累过去，假如多出来的部分是负的则会欠债，而且这个相差的值是会每次累计到总成本里面的。
这样做是错的，因为不能保证最大的数就一定是边界，也就是最大的数不一定不从其他地方接收牌。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, t;
int x[200005];
int y[200005];
ll calc_c() {
int maxid = 0;
for(int j = 1; j <= m; ++j) {
if(y[j] > y[maxid])
maxid = j;
}
int mean = t / m;
ll sum = 0, cur = 0;
for(int j = maxid, k = 1; k <= m; ++j, ++k) {
cur += y[j] - mean;
sum += abs(cur);
}
ll tsum = sum;
sum = 0, cur = 0;
for(int j = maxid + m, k = 1; k <= m; --j, ++k) {
cur += y[j] - mean;
sum += abs(cur);
}
return min(sum, tsum);
}
ll calc_r() {
int maxid = 0;
for(int i = 1; i <= n; ++i) {
if(x[i] > x[maxid])
maxid = i;
}
int mean = t / n;
ll sum = 0, cur = 0;
for(int i = maxid, k = 1; k <= n; ++i, ++k) {
cur += x[i] - mean;
sum += abs(cur);
}
ll tsum = sum;
sum = 0, cur = 0;
for(int i = maxid + n, k = 1; k <= n; --i, ++k) {
cur += x[i] - mean;
sum += abs(cur);
}
return min(sum, tsum);
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d%d%d", &n, &m, &t);
for(int ti = 1; ti <= t; ++ti) {
int u, v;
scanf("%d%d", &u, &v);
x[u]++, x[u + n]++;
y[v]++, y[v + m]++;
}
if((t % n) && (t % m))
printf("impossible");
else {
ll sum = 0;
if(t % n) {
printf("column");
sum = calc_c();
} else if(t % m) {
printf("row");
sum = calc_r();
} else {
printf("both");
sum = calc_r() + calc_c();
}
printf(" %lld\n", sum);
}
}
正确的做法是尝试枚举这个不从其他地方接收牌的点，考虑他对原数组的影响。设这个点为k，则为
\[\sum\limits_{i=1}^{m}|S[i]-S[k]|\] 的最小值
问题变成了“货仓选址”