背景
七夕节因牛郎织女的传说而被扣上了「情 人节」的帽子。于是 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， 接下来输出最小交换次数，与字符串之间用一 个空格隔开。
思路
分行和列，做环上的均分纸牌问题。
用前缀和找出将环切成链的切分点，前缀和的中位数所在位置即为所求。
代码
写的比较丑，见谅…
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
struct node{
int val,pos;
};
bool operator < (node a,node b){
return a.val<b.val;
}
int n,m,t,col[100010],row[100010],ans=0;
node prer[100010],prec[100010];
bool column=false,rowb=false;//row行 col列
int main(){
memset(col,0,sizeof(col));
memset(row,0,sizeof(row));
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
int c,r;
scanf("%d%d",&r,&c);
col[c]+=1; row[r]+=1;
}
//for(int i=1;i<=m;i++) prec[i]=prec[i-1]+col[i];
if(t%m==0) column=true;
if(t%n==0) rowb=true;
if(column&&rowb) printf("both");
else if(column) printf("column");
else if(rowb) printf("row");
else printf("impossible");
if(rowb){
int avg=t/n;
prer[0].val=0;
for(int i=1;i<=n;i++) {
prer[i].val=prer[i-1].val+row[i];
prer[i].pos=i;
}
sort(prer,prer+n);
int k;
if(!n%2) k=prer[n/2].pos;
else k=prer[(n+1)/2].pos;
for(int i=k;i<=k+n-1;i++){
int cur=i%n;
if(cur==0) cur=n;
int next=(i+1)%n;
if(next==0) next=n;
int temp=avg-row[cur];
row[cur]+=temp;
row[next]-=temp;
ans+=abs(temp);
}
}
if(column){
int avg=t/m;
prec[0].val=0;
for(int i=1;i<=m;i++) {
prec[i].val=prec[i-1].val+col[i];
prec[i].pos=i;
}
sort(prec,prec+n);
int k;
if(!m%2) k=prer[m/2].pos;
else k=prer[(m+1)/2].pos;
for(int i=k;i<=k+m-1;i++){
int cur=i%m;
if(cur==0) cur=m;
int next=(i+1)%m;
if(next==0) next=m;
int temp=avg-col[cur];
col[cur]+=temp;
col[next]-=temp;
ans+=abs(temp);
}
}
if(column||rowb) printf(" %d",ans);
return 0;
}