AcWing 105. 七夕祭
原题链接
困难
作者:
lqmm1
,
2021-12-04 10:57:59
,
所有人可见
,
阅读 239
/*
这题刚看到题目的时候很像一个数学结论就是如果我们的糖果数可以被行整除我们一定可以让行上的糖果数一样列也是
看清题目问的问题后发现这个题目的重点不在于能不能均分而在于最小的次数
由于行和列是独立的所以我们可以分别去看行和列
面对行的时候我们可以把一行的糖果看成一个位置有很多糖果然后每次可以移动一个且是一个环形
标准的环形均分问题
*/
#include<stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 3e5+10;
int hang[N],lie[N];
int c[N];
int si[N];
int n,m,k;
int work1(int n,int flag)
{
if(flag==1)
{
for(int i=1;i<=n;i++)
{
si[i]=si[i-1]+hang[i];
}
if(si[n]%n!=0)return -1;
c[1]=0;
int aver=si[n]/n;
for(int i=2;i<=n;i++)
{
c[i]=si[i-1]-(i-1)*aver;
}
int res=0;
sort(c+1,c+n+1);
for(int i=1;i<=n;i++)
{
res+=abs(c[i]-c[n/2+1]);
}
return res;
}
else
{
for(int i=1;i<=n;i++)
{
si[i]=si[i-1]+lie[i];
}
if(si[n]%n!=0)return -1;
c[1]=0;
int aver=si[n]/n;
for(int i=2;i<=n;i++)
{
c[i]=si[i-1]-(i-1)*aver;
}
sort(c+1,c+n+1);
int res=0;
for(int i=1;i<=n;i++)
{
res+=abs(c[i]-c[n/2+1]);
}
return res;
}
}
signed main()
{
cin >> n>>m>>k;
for(int i=1;i<=k;i++)
{
int x,y;
cin >> x>>y;
hang[x]++,lie[y]++;
}
int d1=work1(n,1);
int d2=work1(m,2);
if(d1!=-1&&d2!=-1)
{
cout << "both"<<" ";
cout << d1+d2<<endl;
}
else if(d1==-1&&d2==-1)
{
cout << "impossible"<<endl;
}
else
{
if(d2==-1)
{
cout << "row"<<" ";
cout << d1<<endl;
}
else
{
cout << "column"<<" ";
cout << d2<<endl;
}
}
return 0;
}