AcWing 105. 七夕祭(c++
原题链接
困难
作者:
crucal
,
2023-01-11 15:08:35
,
所有人可见
,
阅读 141
![七夕祭png.png](https://cdn.acwing.com/media/article/image/2023/01/11/203857_d1f9c37991-七夕祭png.png)
#### C++ 代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N=1e5+10;
int n, m;
int row[N], col[N], s[N], c[N];
//列和行是相对独立的,所以我们可以分开写
inline int 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);
int res=0;
//求出中位数到所有点的距离
for (int i=1;i<=n;i++) res+=abs(c[i]-c[(n+1)/2]);
return res;
}
signed main()
{
int cnt=0;
cin>>n>>m>>cnt;
while(cnt--)
{
int x, y;
cin>>x>>y;
row[x]++, col[y]++;
}
int r=work(n, row);
int t=work(m, col);
if(r!=-1 && t!=-1) printf("both %lld\n", r+t);
else if(r!=-1) printf("row %lld\n", r);
else if(t!=-1) printf("column %lld\n", t);
else puts("impossible");
return 0;
}