BZOJ3032权限题
题意：矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分t个摊点感兴趣。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。
分析：行与列是可以独立进行互不影响的.以行为例，结合“均分纸牌”的思想，首先如果t不能被n整除，则肯定无法均分.设hang[i]表示初始时第i行感兴趣的摊点的数量，设(A1[i]=hang[i]-t/n)，设(S1[i])表示A1的前缀和，则不考虑环形的话，(ans1=sum_{i=1}^m|S1[i]|).但是题目是“环形均分纸牌”，所以我们要在环上找到一个断点使之变成普通的均分纸牌，假设从第k行断开，则(ans1=sum_{i=1}^m|S1[i]-S1[k]|),结合“货仓选址”的思想，这个(S1[k])就是将S1数组sort排序后的中位数.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
int hang[N],lie[N];
LL ans1,ans2,A1[N],S1[N],A2[N],S2[N];
int main(){
int n=read(),m=read(),t=read();
for(int i=1;i<=t;++i){
int x=read(),y=read();
++hang[x];++lie[y];
}
int bj1=1,bj2=1;
if(t%n)bj1=0;
else{
int ave1=t/n;
for(int i=1;i<=n;++i){
A1[i]=hang[i]-ave1;
S1[i]=S1[i-1]+A1[i];
}
sort(S1+1,S1+n+1);
int cnt1;
if(n&1)cnt1=S1[(n+1)/2];
else cnt1=S1[n/2];
for(int i=1;i<=n;++i)
ans1+=abs(S1[i]-cnt1);
}
if(t%m)bj2=0;
else{
int ave2=t/m;
for(int i=1;i<=m;++i){
A2[i]=lie[i]-ave2;
S2[i]=S2[i-1]+A2[i];
}
sort(S2+1,S2+m+1);
int cnt2;
if(m&1)cnt2=S2[(m+1)/2];
else cnt2=S2[m/2];
for(int i=1;i<=m;++i)
ans2+=abs(S2[i]-cnt2);
}
if(bj1&&bj2)printf("both %lld
",ans1+ans2);
else if(!bj1&&bj2)printf("column %lld
",ans1+ans2);
else if(bj1&&!bj2)printf("row %lld
",ans1+ans2);
else printf("impossible
");
return 0;
}