七夕祭（中位數）

題面：

七夕祭

思路：

1、左右交換不影響行，上下交換不影響列，行和列分開讨論

2、參考糖果傳遞，明白中位數的意義，糖果傳遞

3、題目可轉換為求|x1-c1|+|x1-c2|+|x1-c3|+…+|x1-cn|的最小（分别對行和列）

其中c1=0, c2=A1-ave, c3=a1+a2-2ave（其中ave為每個位置的最終數值（和除以個數）），以此類推。

4、即為求中位數

代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int n, m, t, x, y;
int h[maxn], l[maxn];
int  sum[maxn], c[maxn];

ll Fun(int a[], int n){
	for(int i=1; i<=n; i++)
		sum[i]=sum[i-1]+a[i];
	if(sum[n]%n)
		return -1;
	ll ave=sum[n]/n;
	c[1]=0;
	for(int i=2; i<=n; i++)
		c[i]=sum[i-1]-(i-1)*ave;
	sort(c+1, c+1+n);
	ll step=0;
	ll zd=c[(n+1)/2];
	for(int i=1; i<=n; i++)
		step+=abs(c[i]-zd);
	return step;
}

int main(){
	scanf("%d%d%d", &n, &m, &t);
	for(int i=0; i<t; i++){
		scanf("%d %d", &x, &y);
		h[x]++;
		l[y]++;
	}
	ll nx=Fun(h, n);
	ll my=Fun(l,m);
	if(nx!=-1&&my!=-1)
		printf("both %lld", nx+my);
	else if(nx!=-1)
		printf("row %lld", nx);
	else if(my!=-1)
		printf("column %lld", my);
	else 
		printf("impossible");
	printf("\n");
	return 0;
}