Acwing105七夕祭解题报告

发布于 2021-11-01  669 次阅读


这道题之前看过,不过没写出来,今天这个坑算是补上了

建议先看一下糖果传递这道题的解题思路,可以说这道题就是和目前这道题是等价的了。

#include <bits/stdc++.h>
using namespace std;
int n,m,t;
int x[150000],y[150000];
long long ans;
void solve1(){
	int tmp[150000];
	tmp[0]=0;
	for(int i=1;i<=n;i++){
		tmp[i]=0;
		tmp[i]=tmp[i-1]+t/n-x[i];
	}
	sort(tmp+1,tmp+1+n);
	for(int i=1;i<=n;i++){
		ans+=abs(tmp[n/2+1]-tmp[i]);
	}
}
void solve2(){
	int tmp[150000];
	tmp[0]=0;
	for(int i=1;i<=m;i++){
		tmp[i]=0;
		tmp[i]=tmp[i-1]+t/m-y[i];
	}
	sort(tmp+1,tmp+1+m);
	for(int i=1;i<=m;i++){
//		cout<<tmp[i]<<" ";
		ans+=abs(tmp[m/2+1]-tmp[i]);
	}
	//cout<<endl;
}
int main(){
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=t;i++){
		int xx,yy;
		cin>>xx>>yy;
		x[xx]++,y[yy]++;
	}
	if((t%n)&&(t%m)){
		cout<<"impossible";
		return 0;
	}
	if(!(t%n)&&!(t%m)) cout<<"both";
	else if(!(t%n)) cout<<"row";
	else cout<<"column";
	cout<<" ";
	if(!(t%n)){
		solve1();
	}
	if(!(t%m)){
		solve2();
	}
	cout<<ans;
	return 0;
}

回忆这理想不够理想,沿途逛世间一趟只有向上