环形均分纸牌问题

题目：

有 n个小朋友坐成一圈，每人有 a[i] 张纸牌。

每人只能给左右两人传纸牌。

每人每次传一张纸牌的代价为1。

求使所有人获得均等纸牌的最小代价。

思路：

因为所有人均等纸牌，所以最后每个人的纸牌数量都等于avg=sum/n。

则使所有人获得均等纸牌的最小代价(ans)=min{|num[1]|+|num[2]|+|num[3]|+```+|num[n]|}。

设num[i]表示第i个人给第i-1个人的纸牌数量，当num[i]为负时表示第i-1个人给第i个人的纸牌数量。

特别的，num[1]表示第1个人给第n个人的纸牌数量。

则每个人最后的纸牌数量=每个人最初的纸牌数量+别人给他的纸牌数量-他给别人的纸牌数量。

a[1]+num[2]-num[1]=avg;

a[2]+num[3]-num[2]=avg;

...

a[i]+num[i+1]-num[i]=avg;

移项得：
num[2]=num[1]-(a[1]-avg);

num[3]=num[2]-(a[2]-avg)=num[1]-(a[1]-avg)-(a[2]-avg);

...

num[n]=num[1] -  

令num[1]后面的部分为c[i]。

则c[1]=a[1]-avg;

c[2]=a[1]-avg+(a[2]-avg);

```c[i]=c[i-1]+(a[i]-avg);

则num[i]=num[1]-c[i];

则ans=min{|num[1]-c[1]|+|num[1]-c[2]|+...+|num[1]-c[n-1]|};

因为|num[1]-c[i]|的几何意义是num[1]到c[i]的距离，即要在数轴上找一个点num[1]使得它到其他点{c[1],c[2],... c[n-1]}的距离之和最小，所以问题转化为货仓选址。

那么选择的num[1]应该为c[i]的中位数。

步骤：

（1）先求出平均数avg；

（2）用a[i]-avg；

（3）求出前缀和数组c[i]=a[i-1]+a[i]；

（4）求出中位数mid=c[(n+1)>>1]；

（5）转化为货仓选址问题，ans+=abs(mid-c[i])；

模板：

ll get(int *a,int n){
	ll sum=0;//和 
	for(int i=1;i<=n;i++) sum+=a[i];
	sum/=n;//平均数 
	for(int i=1;i<=n;i++) a[i]-=sum;//减去平均数 
	c[1]=0;
	for(int i=2;i<=n;i++) c[i]=c[i-1]+a[i];//前缀和 
	//货仓选址问题 
	sort(c+1,c+n+1);//排序 
	int mid=c[(n+1)>>1];//中位数 
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=abs(mid-c[i]);
	return ans;
}

例题：

七夕祭

思路：

单独考虑行和列，仅当k能整除行数（列数时）才行。

然后转化为环形均分纸牌问题。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int a[N],b[N],n,m,k; 
ll c[N];
 
ll get(int *a,int n){
	ll sum=0;//和 
	for(int i=1;i<=n;i++) sum+=a[i];
	sum/=n;//平均数 
	for(int i=1;i<=n;i++) a[i]-=sum;//减去平均数 
	c[1]=0;
	for(int i=2;i<=n;i++) c[i]=c[i-1]+a[i];//前缀和 
	//货仓选址问题 
	sort(c+1,c+n+1);//排序 
	int mid=c[(n+1)>>1];//中位数 
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=abs(mid-c[i]);
	return ans;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	a[x]++,b[y]++;
	}
	if(k%n&&k%m){
		puts("impossible");
	}
	else if(k%n){
		printf("column %lld\n",get(b,m));
	}
	else if(k%m){
		printf("row %lld\n",get(a,n));
	}
	else {
		printf("both %lld\n",get(a,n)+get(b,m));
	}
	return 0;
}