http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0502%20%E4%B8%83%E5%A4%95%E7%A5%AD
一 在解題之前，先了解一下中位數的用處。
先看一下這個題：http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0501%20%E8%B4%A7%E4%BB%93%E9%80%89%E5%9D%80
我們要在這一條數軸選一個地點，使其到其它所有的點的距離之和最小。那麼這個點就是所有點的中位數。證明的話我們可以采用反證法：
假設我們選擇X點，在X點的左邊有p個點，右邊有q個點。如果p>q，那麼當我們把X往左邊移動y個點時，距離之和就會變小q-p；反之如果q<p,那麼往右邊移動就會減小距離之和。故q==p時，距離之和最小。
二 回到本題來：
當我們交換左右的時候，我們改變某兩列發的情況，對行并沒有改變。同理交換上下的時候，對列也沒有改變。故可以考慮，這兩者并沒有什麼影響。
那現在讓我們考慮交換左右的情況，共有m列。如果他感興趣的攤位的個數不能整除m時，那顯然這個時候我們是不能通過交換左右的位置來使每一列都想等的。如果感興趣的攤位能夠整除m時，我們又怎樣求最少的交換次數呢。說到這裡我們不得不提一下“均分紙牌”：
有m個人，每個人有c[i]張牌，每個人每次可以把自己手中的一張牌交給他相鄰的人。問最少多少步操作可以使得每個人擁有的紙牌數相同。（我們認為最後一定是可以均分的）。那現在我們假設最後每個人都均分到k張牌。故第一個人所做的操作就是c[1]-k(這k張牌可能是他給第二個人的，也可能是第二個人給他的)，第二個人所做的操作為 從c[1]+c[2]-k*2;第三個人為c[1]+c[2]+c[3]-k*3;故總的操作為
，g[i]是c[i]的字首和。現在我們先把c[i]都減去k，令A[i]=c[i]-k,則答案可以寫為
，其中s[i]是A[i]的字首和。
好了好了，再次回到本題，本體中，第一列和最後一列是可以交換的，故構成了一個環。但其實其中有兩個人之間是沒有交換操作的，比如我們從第i個人開始操作，那麼對第i個人處理之後第i個人就是已經滿足條件了，當我們循環到最後一個人時（i前面的一個人），那們這個人也肯定也滿足條件了，如果他不滿足條件的話，假設他需要進行w次操作才能滿足條件，那就會導緻第i個人不滿條件了，故第i個人和他之前的人肯定是沒有進行交換的。這樣的話，我們就可以枚舉這個斷點了。如果在第k個人之後把這個環斷開，那這m個人持有的紙牌數，字首和分别是：
A[k+1] s[k+1]-s[k]
A[k+2] s[k+2]-s[k]
...............................................
A[m] s[1]+s[m]-s[k]
...............................................
A[k] s[k]+s[m]-s[k]
這裡的A是減去均分k之後數。
是以答案就是
。那k取什麼值時答案最小呢？仔細看一看上面這個式子，是不是和開始講的中位數很像，沒錯，就是中位數。
好了，上代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const long long MAXN = 100000 + 10;
long long d[MAXN], c[MAXN],sum[MAXN];
long long n, m, k;
long long solve(long long a[MAXN], long long n) {
long long k=a[0]/n;
for (long long i = 1; i <=n; i++) {
a[i] = a[i] - k;
sum[i] = sum[i - 1] + a[i];
}
sort(sum+1,sum+1+n);
long long ans=0;
for (long long i = 1; i <= n; i++)ans += abs(sum[i]-sum[(n+1)/2]);
return ans;
}
int main() {
cin >> n >> m >> k;
long long a, b;
for (long long i = 1; i <= k; i++) {
cin >> a >> b;
d[a]++; c[b]++;
}
for (long long i = 1; i <= n; i++)d[0] += d[i];
for (long long i = 1; i <= m; i++)c[0] += c[i];
if (d[0] % n == 0 && c[0] % m == 0)
printf("both %lld\n", solve(d, n) + solve(c, m));
else if (d[0] % n == 0)
printf("row %lld\n", solve(d, n));
else if (c[0] % m == 0)
printf("column %lld\n", solve(c, m));
else
printf("impossible\n");
return 0;
}