排序1:七夕祭
作者:
总打瞌睡的天天啊
,
2024-08-05 14:45:46
,
所有人可见
,
阅读 2
//主要还是看思路,将过程一步步拆解
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100010;
int row[N],col[N],s[N],c[N];
LL work(int n,int a[])
{
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
if(s[n]%n)return -1;
int avg=s[n]/n;
c[1]=0;
for(int i=2;i<=n;i++)c[i]=s[i-1]-(i-1)*avg;
sort(c+1,c+n+1);
LL res=0;
for(int i=1;i<=n;i++)res+=abs(c[i]-c[(n+1)/2]);
return res;
}
int main()
{
int n,m,t;
cin>>n>>m>>t;
while(t--)
{
int x, y;
cin>>x>>y;
row[x]++,col[y]++;
}
LL r=work(n,row);
LL c=work(m,col);
if(r!=-1&&c!=-1)cout<<"both "<<r+c<<endl;
else if(r!=-1)cout<<"row "<<r<<endl;
else if(c!=-1)cout<<"column "<<c<<endl;
else cout<<"impossible"<<endl;
return 0;
}