AcWing 105. 七夕祭
原题链接
困难
作者:
一抹斜阳
,
2020-03-04 22:06:18
,
所有人可见
,
阅读 701
//类似于分糖果
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m,t;
int x[N];
int y[N];
int row[N];
int column[N];
long long c[N];
int main()
{
cin>>n>>m>>t;
for(int i = 1;i <= t;i++)
{
scanf("%d",&x[i]);
scanf("%d",&y[i]);
row[x[i]]++;
column[y[i]]++;
}
if((t % n !=0) && (t % m != 0))
{
printf("impossible\n");
}
else if(t % n != 0)
{
int avg = t/m;
for(int i = 2;i<=m;i++)
{
c[i] = c[i-1] + avg -column[i];
}
sort(c+1,c+m+1);
long long coun = 0;
int k = 1 + m >>1;
for(int i = 1;i <= m;i++)
{
coun += abs(c[k] - c[i]);
}
cout<<"column "<<coun<<endl;
}
else if(t %m != 0)
{
int avg = t/n;
for(int i = 2;i<=n;i++)
{
c[i] = c[i-1] + avg -row[i];
}
sort(c+1,c+n+1);
long long coun = 0;
int k = 1 + n >>1;
for(int i = 1;i <= n;i++)
{
coun += abs(c[k] - c[i]);
}
cout<<"row "<<coun<<endl;
}
else
{
int avg = t/m;
for(int i = 2;i<=m;i++)
{
c[i] = c[i-1] + avg -column[i];
}
sort(c+1,c+m+1);
long long coun1 = 0;
int k = 1 + m >>1;
for(int i = 1;i <= m;i++)
{
coun1 += abs(c[k] - c[i]);
}
for(int i = 1;i<=m;i++)
{
c[i] = 0;
}
avg = t/n;
for(int i = 2;i<=n;i++)
{
c[i] = c[i-1] + avg -row[i];
}
sort(c+1,c+n+1);
long long coun2 = 0;
k = 1 + n >>1;
for(int i = 1;i <= n;i++)
{
coun1 += abs(c[k] - c[i]);
}
long long coun = coun1 + coun2;
cout<<"both "<<coun<<endl;
}
return 0;
}