七夕祭

目录

• 思路
• 错误原因
• 代码

思路

神仙题（虽然是例题）
这道题目有一个非常重要的性质就是，只会改变相邻的两个数的位置，因此我们交换两个数，
只会改变一行的喜爱小摊或者一列的喜爱小摊，而不会同时改变行和列的喜爱小摊，既然这样的话，
我们就可以将这道题目分成两个部分，一部分是求行的最少次数，一部分是求列的最少次数。

这道题就是环形的均分纸牌（做法相同都是求出与目标答案的差值），通过记录前缀和，然后排序
直接取在中位数上的一道神仙题

本题融合了“货仓选址”和“均分纸牌”，是一道不错的题目

错误原因

复制(checkr())写(checkc())忘了把n改成m了,咕咕咕
而且我觉得我对(r)和(c)有点搞不清楚,就像二分的(l,r)一样

代码

丑陋不堪，有很多调试用的宏，不喜勿喷

#include<bits/stdc++.h>
#define int long long int
#define fre
//#define couts
//#define zong
//#define heng
using namespace std;
const int N=100000+2019;
int row[N],column[N],r,c,ans1,ans2,n,m,t;
int flagr,flagc;
int s[N];//前缀和
#ifndef zong
int checkr() { //处理横排
	memset(s,0,sizeof(s));
	if(t%n!=0) return 0;
	r/=n;//求平均数
	for(int i=1; i<=n; ++i) {
		row[i]-=r,s[i]=s[i-1]+row[i];//做差，求前缀和
	}
	sort(s+1,s+1+n);
	int mid=(1+n)>>1;
	for(int i=1; i<=n; ++i) ans1+=abs(s[i]-s[mid]); //直接取中位数求答案即可
	return 1;
}
#endif

#ifndef heng
int checkc() { //处理纵排
	memset(s,0,sizeof(s));
	if(t%m!=0) return 0;
	c/=m;//求平均数
	for(int i=1; i<=m; ++i) {
		column[i]-=c,s[i]=s[i-1]+column[i];//做差，求前缀和
	}
	sort(s+1,s+1+m);
	int mid=(1+m)>>1;
	for(int i=1; i<=m; ++i) ans2+=abs(s[i]-s[mid]); //直接取中位数求答案即可
	return 1;
}
#endif
signed main() {
	#ifndef fre
	freopen("a.in","row",stdin);
	freopen("a.out","w",stdout);
	#endif
	cin>>n>>m>>t;
	for(int i=1; i<=t; ++i) {
		int x,y;
		scanf("%lld%lld",&x,&y);
		row[x]++,column[y]++;
		r++,c++;
	}
	flagr=checkr();
	flagc=checkc();
	#ifndef couts
	if(flagc&&flagr) cout<<"both";
	else if(flagr) cout<<"row";
	else if(flagc) cout<<"column";
	else cout<<"impossible";
	#endif
	if(flagr||flagc) cout<<" "<<ans1+ans2;
	return 0;
}