题目描述
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是TYVJ今年举办了一次线下七夕祭。
Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的形式很像。
矩形的祭典会场由N排M列共计N×M个摊点组成。
虽然摊点种类繁多,不过cl只对其中的一部分摊点感兴趣,比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。
Vani预先联系了七夕祭的负责人zhq,希望能够通过恰当地布置会场,使得各行中cl感兴趣的摊点数一样多,并且各列中cl感兴趣的摊点数也一样多。
不过zhq告诉Vani,摊点已经随意布置完毕了,如果想满足cl的要求,唯一的调整方式就是交换两个相邻的摊点。
两个摊点相邻,当且仅当他们处在同一行或者同一列的相邻位置上。
由于zhq率领的TYVJ开发小组成功地扭曲了空间,每一行或每一列的第一个位置和最后一个位置也算作相邻。
现在Vani想知道他的两个要求最多能满足多少个。
在此前提下,至少需要交换多少次摊点。
算法:贪心 前缀和 公式递推
时间复杂度:$3N+Nlog(N)$
(1) 将行和列分别看成独立的操作
(2) 一维的环形均分问题可看参考题目:https://www.acwing.com/problem/content/124/
C++代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int row[N],col[N],s[N],c[N];
LL execute(int a[],int n)
{
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+1+n);
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,cnt;
scanf("%d%d%d",&n,&m,&cnt);
for(int i=0;i<cnt;i++){
int r,c;
scanf("%d%d",&r,&c);
row[r]++,col[c]++;
}
LL r=execute(row,n);
LL c=execute(col,m);
if(r!=-1 && c!=-1)printf("both %lld\n",r+c);
else if(r!=-1)printf("row %lld\n",r);
else if(c!=-1)printf("column %lld\n",c);
else printf("impossible\n");
return 0;
}