題目：
背景
七夕節因牛郎織女的傳說而被扣上了「情人節」的帽子。于是JoyOI今年舉辦了一次線下七夕祭。Vani同學今年成功邀請到了cl同學陪他來共度七夕，于是他們決定去JoyOI七夕祭遊玩。
描述
JoyOI七夕祭和11區的夏祭的形式很像。矩形的祭典會場由N排M列共計N×M個攤點組成。雖然攤點種類繁多，不過cl隻對其中的一部分攤點感興趣，比如章魚燒、蘋果糖、棉花糖、射的屋……什麼的。Vani預先聯系了七夕祭的負責人zhq，希望能夠通過恰當地布置會場，使得各行中cl感興趣的攤點數一樣多，并且各列中cl感興趣的攤點數也一樣多。
不過zhq告訴Vani，攤點已經随意布置完畢了，如果想滿足cl的要求，唯一的調整方式就是交換兩個相鄰的攤點。兩個攤點相鄰，當且僅當他們處在同一行或者同一列的相鄰位置上。由于zhq率領的JoyOI開發小組成功地扭曲了空間，每一行或每一列的第一個位置和最後一個位置也算作相鄰。現在Vani想知道他的兩個要求最多能滿足多少個。在此前提下，至少需要交換多少次攤點。
輸入格式
第一行包含三個整數N和M和T。T表示cl對多少個攤點感興趣。
接下來T行，每行兩個整數x, y，表示cl對處在第x行第y列的攤點感興趣。
輸出格式
首先輸出一個字元串。如果能滿足Vani的全部兩個要求，輸出both；如果通過調整隻能使得各行中cl感興趣的攤點數一樣多，輸出row；如果隻能使各列中cl感興趣的攤點數一樣多，輸出column；如果均不能滿足，輸出impossible。
如果輸出的字元串不是impossible， 接下來輸出最小交換次數，與字元串之間用一個空格隔開。
樣例輸入1
2 3 4
1 3
2 1
2 2
2 3
樣例輸入2
3 3 3
1 3
2 2
2 3
樣例輸出1
row 1
樣例輸出2
both 2
解析：
這道題就類似于均分紙牌的問題：一行n個人，給你每個人有的紙牌數，每個人可以向他旁邊的人遞紙牌，每次遞1張，最少需要遞送多少次能使全部人擁有同樣多的紙牌。
解法就是：就是每次隻考慮滿足一個人，從頭開始，每個人從下一個人處拿或者給紙牌直到這個人的牌數等于平均值（不用管下一個人是正是負）
設第i個人擁有的紙牌為a【i】，算出最終每個人平均的紙牌數為flag，令每一個a【i】減去flag，計算a的字首和sum[i]，最後将sum的絕對值都加起來就是答案。
雖然可以直接強行計算每一個a【i】-flag 的絕對值再加起來，但是對于另外的題來說這種做法就不太友善了。
對于本題來說，每一行的之間的交換不會影響列，每一列的交換同理，是以可以将行和列單獨的分開操作，那麼就隻考慮行的情況。
首先我們考慮兩種攤位擺放情況，看看是否一樣。
第一種情況會不會互相擋住呢？因為假如需要向上交換那麼一定是上面那一排向上交換，交換之後就沒有東西擋住下面那一行了，向下交換也是一樣，是以這兩種情況操作起來都是一樣的。
那麼就可以轉化問題了：設行數為n，攤位數為k，給你每一行的攤位數，問至少操作幾次可以将攤位均分，對于某一行的操作可以是該行向上或者向下交換一個攤位。
首先很明顯，可以均分的條件是n%k==0，
然後此題就很類似于紙牌均分的問題，唯一的不同就是此題是一個環，首先我們就将行看成點，因為沒有特定的起點，我們需要找到一個特定的起點将問題轉化為紙牌均分問題。
假如存在兩個點，他們之間不需要交換攤位，那麼就可以将這兩點中間拆開，将環變成線。事實上在環中一定會存在這樣的情況，那麼如何證明呢？
我們利用反證法，假設存在這樣一個環兩兩之間都需要交換攤位才能平衡，随便選擇一個點作為開頭，由于交換的方法直接從下一個點拿或者給攤位使得該點的攤位等于平均值，而按照假設這個點的前一個點一定又會與它發生攤位交換，是以該點不等于平均值，與條件不符，假設不成立。
是以環中每兩個點都可以做到不交換攤位，取決的是你交換攤位的方法。
我們假設第x個點之後分割環變成線可以取得最優解，設i點的攤位數為a[i]，最終攤位的平均值為flag，我們先将每個a[i]減去平均值flag，然後求a[i]的字首和為s[i]，那麼對于從x開始的情況就有：
根據答案=每一個字首和的絕對值之和，又因為s[n]=0（每個a都減去flag，最後肯定平衡啊），是以我們可以得出
問題轉化到這裡就很簡單了，最後就是求這個ans的式子的最小值。
最後這個式子就相當于将每一個s【i】鋪在數軸上，然後找到一個點i使得點i到每一點的距離之和最小。
先考慮s[1] 和 s[n]這兩點，很明顯當點位于s[i]和s[n]之間時到這兩點的距離之和最短，恒等于abs(s[n]-s[1])
接着考慮s[2]和s[n-1]，同理。
最後就直到當n為奇數的時候，i=(n+1)/2這個點是最優解，當n為偶數的時候，i=n/2 或者 i=n/2 +1 這兩點都是最優解。
是以我們隻需要将s排序然後找中間那個點，按着式子計算就好了
代碼：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;
ll hang[maxn], lie[maxn];
int main() {
int *now;
int n, m, t; cin >> n >> m >> t;
ll flag1 = 1LL*t / n, flag2 = 1LL*t / m;
for (register int i = 1; i <= t; i++) {
int inp1, inp2;
scanf("%d %d", &inp1, &inp2);
hang[inp1]++;
lie[inp2]++;
}
for (register int i = 1; i <= n; i++) { // 減去平均值再求字首和
hang[i] -= flag1;
hang[i] += hang[i - 1];
}
for (register int i = 1; i <= m; i++) {
lie[i] -= flag2;
lie[i] += lie[i - 1];
}
sort(hang + 1, hang + n + 1); //排序找中間數
sort(lie + 1, lie + m + 1);
ll ans = 0;
int xixi;
if (t%n == 0) { //對行解答
xixi = (n+1) /2;
for (register int i = 1; i <= n; i++) {
ans += abs(hang[i] - hang[xixi]);
}
}
if (t%m == 0) { //對列解答
xixi = (m+1) /2;
for (register int i = 1; i <= m; i++) {
ans += abs(lie[i] - lie[xixi]);
}
}
if (t%n == 0 && t%m != 0) {
printf("row ");
}
else if (t%m == 0 && t%n != 0) {
printf("column ");
}
else if (t%m && t%n) {
printf("impossible\n");
return 0;
}
else {
printf("both ");
}
printf("%lld\n",ans);
return 0;
}