七夕祭

目录

• 思路
• 错误原因
• 代码

思路

神仙题（虽然是例题）
这道题目有一个非常重要的性质就是，只会改变相邻的两个数的位置，因此我们交换两个数，
只会改变一行的喜爱小摊或者一列的喜爱小摊，而不会同时改变行和列的喜爱小摊，既然这样的话，
我们就可以将这道题目分成两个部分，一部分是求行的最少次数，一部分是求列的最少次数。

这道题就是环形的均分纸牌（做法相同都是求出与目标答案的差值），通过记录前缀和，然后排序
直接取在中位数上的一道神仙题

本题融合了“货仓选址”和“均分纸牌”，是一道不错的题目

错误原因

复制$checkr()$写$checkc()$忘了把n改成m了,咕咕咕
而且我觉得我对$r$和$c$有点搞不清楚,就像二分的$l,r$一样

代码

丑陋不堪，有很多调试用的宏，不喜勿喷

#include<bits/stdc++.h>
#define int long long int
#define fre
//#define couts
//#define zong
//#define heng
using namespace std;
const int N=100000+2019;
int row[N],column[N],r,c,ans1,ans2,n,m,t;
int flagr,flagc;
int s[N];//前缀和
#ifndef zong
int checkr() { //处理横排
    memset(s,0,sizeof(s));
    if(t%n!=0) return 0;
    r/=n;//求平均数
    for(int i=1; i<=n; ++i) {
        row[i]-=r,s[i]=s[i-1]+row[i];//做差，求前缀和
    }
    sort(s+1,s+1+n);
    int mid=(1+n)>>1;
    for(int i=1; i<=n; ++i) ans1+=abs(s[i]-s[mid]); //直接取中位数求答案即可
    return 1;
}
#endif

#ifndef heng
int checkc() { //处理纵排
    memset(s,0,sizeof(s));
    if(t%m!=0) return 0;
    c/=m;//求平均数
    for(int i=1; i<=m; ++i) {
        column[i]-=c,s[i]=s[i-1]+column[i];//做差，求前缀和
    }
    sort(s+1,s+1+m);
    int mid=(1+m)>>1;
    for(int i=1; i<=m; ++i) ans2+=abs(s[i]-s[mid]); //直接取中位数求答案即可
    return 1;
}
#endif
signed main() {
    #ifndef fre
    freopen("a.in","row",stdin);
    freopen("a.out","w",stdout);
    #endif
    cin>>n>>m>>t;
    for(int i=1; i<=t; ++i) {
        int x,y;
        scanf("%lld%lld",&x,&y);
        row[x]++,column[y]++;
        r++,c++;
    }
    flagr=checkr();
    flagc=checkc();
    #ifndef couts
    if(flagc&&flagr) cout<<"both";
    else if(flagr) cout<<"row";
    else if(flagc) cout<<"column";
    else cout<<"impossible";
    #endif
    if(flagr||flagc) cout<<" "<<ans1+ans2;
    return 0;
}