Description
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。
不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。
Input
第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。
接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。
Output
首先输出一个字符串。如果能满足Vani的全部两个要求，输出both；如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；如果只能使各列中cl感兴趣的摊点数一样多，输出column；如果均不能满足，输出impossible。
如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。
Sample Input
样例输入1
2 3 4
1 3
2 1
2 2
2 3
样例输入2
3 3 3
1 3
2 2
2 3
Sample Output
样例输出1
row 1
样例输出2
both 2
HINT
对于100% 的数据，1≤N, M≤100000，0≤T≤min(NM, 100000)，1≤x≤N，1≤y≤M。
把横与纵分开来看，他们是不会相互影响的
所以我们把问题转换为一个环，上面有很多堆石子，求最后让每堆石子相同，求最小代价(代价是每次移动的石子数）
这个问题就跟糖果传递一模一样了
设g[i]为当前堆石子要从后面一堆石子拿多少个石子才能达到平均数
那么答案就是sigma（abs（g[i]))1..n
g[i]=avg+g[i-1]-a[i];//a[i]为当前石子堆有多少石子，avg代表平均数
g[i]-g[i-1]=avg-a[i];
sum[i]=g[i]-g[i-1]
tot[i]=sigma(sum[i]);1..i
tot[i]=g[i]-g[n];
g[n]+tot[i]=g[i];
所以答案变成了sigma（abs（tot[i]+g[n]
))1..n
我们把g[n]看成-x
sigma（abs（tot[i]+g[n]
))1..n
=sigma（abs（tot[i]-x))1..n
x等于tot[i]的中位数时sigma（abs（tot[i]-x))1..n最小
tot[i]怎么求
tot[i]=sigma(sum[i]);1..i
=sigma(sum[i]);1..(i-1)+sum[i]
=tot[i-1]+sum[i]
=tot[i-1]+g[i]-g[i-1]
=tot[i-1]+avg-a[i];
tot[0]=0;
最后横竖答案相加
这个用排序来求中位数
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 110000
using namespace std;
int aa[maxn],bb[maxn],tot[maxn],n,m,t,ave;
bool kk1,kk2;
long long ans;
inline int read(){
int tmp=0;char ch;
while(ch=getchar())if('0'<=ch&&ch<='9')break;
for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
return tmp;
}
int main(){
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
int a=read(),b=read();
aa[a]++;bb[b]++;
}
if(t%n)kk1=1;
else{
ave=t/n;
for(int i=1;i<=n;i++)tot[i]=ave-aa[i]+tot[i-1];
sort(tot+1,tot+1+n);
for(int i=1;i<=n;i++)ans+=1LL*abs(tot[i]-tot[n/2+1]);
}
if(t%m)kk2=1;
else{
ave=t/m;
for(int i=1;i<=m;i++)tot[i]=ave-bb[i]+tot[i-1];
sort(tot+1,tot+1+m);
for(int i=1;i<=m;i++)ans+=1LL*abs(tot[i]-tot[m/2+1]);
}
if(kk1&&kk2){printf("impossible");return 0;}
else if(kk1)printf("column");
else if(kk2)printf("row");
else printf("both");
printf(" %I64d",ans);
// system("pause");
return 0;
}
这个用快速选择找中位数
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 100001
using namespace std;
int aa[maxn],bb[maxn],tot[maxn],n,m,t,ave;
bool kk1,kk2;
long long ans;
inline int read(){
int tmp=0;char ch;
while(ch=getchar())if('0'<=ch&&ch<='9')break;
for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
return tmp;
}
int find(int *l,int *r,int rk){
int *i=l,*j=r,mid=*(l+(r-l)/2);
do{
while((*i)<mid)i++;
while((*j)>mid)j--;
if(i<=j){
swap(*i,*j);
i++;j--;
}
}while(i<=j);
if(j-l+1>=rk)return find(l,j,rk);
if(rk>i-l)return find(i,r,rk-(i-l));
return *(l+rk-1);
}
int main(){
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
int a=read(),b=read();
aa[a]++;bb[b]++;
}
if(t%n)kk1=1;
else{
ave=t/n;
for(int i=1;i<=n;i++)tot[i]=ave-aa[i]+tot[i-1];
int tmp=find(tot+1,tot+n,n/2+1);
for(int i=1;i<=n;i++)ans+=1LL*abs(tot[i]-tmp);
}
if(t%m)kk2=1;
else{
ave=t/m;
for(int i=1;i<=m;i++)tot[i]=ave-bb[i]+tot[i-1];
int tmp=find(tot+1,tot+m,m/2+1);
for(int i=1;i<=m;i++)ans+=1LL*abs(tot[i]-tmp);
}
if(kk1&&kk2){printf("impossible");return 0;}
else if(kk1)printf("column");
else if(kk2)printf("row");
else printf("both");
printf(" %I64d",ans);
}