【题目链接】
https://www.lydsy.com/JudgeOnline/problem.php?id=3032
【算法】
交换左右两个相邻格子的摊点，不会改变这一行的摊点个数
交换上下两个相邻格子的摊点，不会改变这一列的摊点个数
因此，题目中所要求的两个问题是独立的，可以分别计算，以第一问 ： 每列摊点个数相等，进行讨论 ：
我们将每列中的初始摊点个数记为Ai，如果感兴趣的摊点总数不能被M整除，则无解，否则，等价于一个“环形均分纸牌”的问题，
如果不允许“环形传递”，那么最少移动步数为 sigma( | Si | ),Si为Ai - T / M的前缀和
如果允许，仔细思考后会发现，一定有一种最优解的方案，使得环上两个人不进行传递，考虑将环断开 ：
假设断开位置为k，那么断开后，每个人的纸牌个数和前缀和分别为 :
Ak+1 Sk+1 - Sk
Ak+2 Sk+2 - Sk
...
Am Sm - Sk
A1 S1 + Sm - Sk
...
Ak Sk + Sm - Sk
因为Sm = 0，所以，前缀和数组与一般情况的差别就是每个位置都减了Sk
所以若断开位置为k，最少交换次数为 ： sigma( | Si - Sk| ) , 当Sk取前缀和数组S的中位数时，这个式子的值最小，也就是说，我们将S数组从小到大排序，取中位数Sk就是最优解
那么，这道题就迎刃而解了！
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 100010 struct pos { int x,y; } a[MAXN]; int i,N,M,T; long long ans; long long s[MAXN]; inline void solve1() { int i; memset(s,0,sizeof(s)); for (i = 1; i <= T; i++) s[a[i].y]++; for (i = 1; i <= M; i++) s[i] -= T / M; for (i = 2; i <= M; i++) s[i] += s[i-1]; sort(s+1,s+M+1); for (i = 1; i <= M; i++) ans += abs(s[i] - s[(M+1)>>1]); } inline void solve2() { int i; memset(s,0,sizeof(s)); for (i = 1; i <= T; i++) s[a[i].x]++; for (i = 1; i <= N; i++) s[i] -= T / N; for (i = 2; i <= N; i++) s[i] += s[i-1]; sort(s+1,s+N+1); for (i = 1; i <= N; i++) ans += abs(s[i] - s[(N+1)>>1]); } int main() { scanf("%d%d%d",&N,&M,&T); for (i = 1; i <= T; i++) scanf("%d%d",&a[i].x,&a[i].y); if (T % N != 0 && T % M != 0) { printf("impossible"); return 0; } if (T % M == 0 && T % N != 0) { printf("column "); solve1(); } else if (T % M != 0 && T % N == 0) { printf("row "); solve2(); } else { printf("both "); solve1(); solve2(); } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/evenbao/p/9237438.html