题目描述
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。不过zhq告诉Vani，摊点已经布置完毕了，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。
输入
第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。
接下来T行，每行两个整数x,y，表示cl对处在第x行第y列的摊点感兴趣。
输出
首先输出一个字符串。如果能满足 Vani 的全部两个要求，输出 both；如果通过调整 只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；如果只能使各列中 cl 感兴趣的摊点 数一样多，输出 column；如果均不能满足，输出 impossible。
如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一 个空格隔开。
样例输入
2 3 4
1 3
2 1
2 2
2 3
样例输出
row 1
1
提示
对于30%的数据，N,M≤100。
对于70%的数据，N,M≤1000。
对于100%的数据，1≤N,M≤100000，0≤T≤min(NM,100000)，1≤x≤N，1≤y≤M。
分析
- 首先不难发现列和行的操作是互不影响的，所以可以分开处理。
- 我们要让所有行变成一样数量的话，这其实是一个“均分纸牌问题”，而且在本题中是环形的。
- 设均分后每个人应有average张纸牌，把每个人现有纸牌数都减去average，那么我们的均分目的及变成了每个人都有0张牌
- 对于非环形的均分纸牌问题，最少移动数是前缀和的绝对值之和；那么对于环形的来说我们可以枚举前缀和开始算的起点，然后取所有答案的最小值。
- 然后我们可以发现，以第一个元素为起点的各个前缀和减去pre[k]之后恰好是以第k+1个元素为起点的各个前缀和。
- 问题转化为减去哪一个pre[k]可以使得前缀和的绝对值最小，也就是(sum_{i=1}^{n}|pre[i]-pre[k]|)最小
- 显然当pre[k]为前缀和数组中位数时最小
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100050;
const ll MOD=1e9+7;
int a[maxn],b[maxn];
ll sum[maxn];
int main()
{
int n,m,t;
scanf("%d%d%d", &n,&m,&t);
for(int i = 0; i < t; ++i){
int x,y;
scanf("%d%d", &x,&y);
a[x]++;
b[y]++;
}
if(t%n&&t%m){
printf("impossible
");
return 0;
}
if(t%n==0&&t%m==0) printf("both ");
else if(t%n==0) printf("row ");
else printf("column ");
ll s1=0,s2=0;
if(t%n==0) {
int p=t/n;
for(int i = 1; i <= n; ++i){
a[i]-=p;
sum[i]=sum[i-1]+a[i];
}
sort(sum+1,sum+1+n);
ll mid=sum[(n+1)/2];
for(int i = 1; i <= n; ++i){
s1+=abs(sum[i]-mid);
}
}
if(t%m==0) {
int p=t/m;
for(int i = 1; i <= m; ++i){
b[i]-=p;
sum[i]=sum[i-1]+b[i];
}
sort(sum+1,sum+1+m);
ll mid=sum[(m+1)/2];
for(int i = 1; i <= m; ++i){
s2+=abs(sum[i]-mid);
}
}
printf("%lld
", s1+s2);
return 0;
}