题目描述

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是TYVJ今年举办了一次线下七夕祭。

Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。

TYVJ七夕祭和11区的夏祭的形式很像。

矩形的祭典会场由N排M列共计N×M个摊点组成。

虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。

不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在Vani想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

输入格式
第一行包含三个整数N和M和T，T表示cl对多少个摊点感兴趣。

接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。

输出格式
首先输出一个字符串。

如果能满足Vani的全部两个要求，输出both；

如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；

如果只能使各列中cl感兴趣的摊点数一样多，输出column；

如果均不能满足，输出impossible。

如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围
$1≤N,M≤100000, 0≤T≤min(N∗M,100000), 1≤x≤N, 1≤y≤M$

样例

输入样例：
2 3 4
1 3
2 1
2 2
2 3
输出样例：
row 1

分治+贪心+前缀和+中位数+排序

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

既然如此的话，这道题目就成为了环形的均分纸牌问题，均分纸牌这是一道经典的贪心问题，可以自行百度理解即可懒惰病发作ing 但是环形均分纸牌问题和普通均分纸牌问题又有不同之处，因此我们要截环为序列，所以说我们可以利用中位数把环形变成区间，具体思路可见《算法竞赛进阶指南》。

感谢@sandychn 大佬指出简短代码中一个小问题.

后更新简短代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(i,a,b) for(ll i=a;i<=b;i++)
const int N=1e5+10;
ll n,m,t,a[N],b[N],f[N],x,y,rr,cc;
ll calc(ll a[],ll n)
{
    fir(i,1,n)
    {
        a[i]-=(a[0]/n);
        f[i]=f[i-1]+a[i];
    }
    sort(f+1,f+1+n);
    ll mid=(n+1)>>1,ans=0;//不是n|1,因为n若为奇数会出问题.不过这道题目也不会出现问题.因为中位数只要求是最中间,但是如果说我们要求出n+1的话,那么不能用n|1. 感谢@sandychn 大佬指出问题.
    fir(i,1,n)
        ans+=abs(f[mid]-f[i]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>x>>y;
        a[x]++;
        b[y]++;
    }
    fir(i,1,n)
        a[0]+=a[i];
    fir(i,1,m)
        b[0]+=b[i];
    ll as=a[0]%n,bs=b[0]%m;
    if (!as && !bs)
        cout<<"both "<<calc(a,n)+calc(b,m);
    else if(!as)
        cout<<"row "<<calc(a,n);
    else if(!bs)
        cout<<"column "<<calc(b,m);
    else
        cout<<"impossible";
    return 0;
}

lyd老师的精简C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int u=100010; 
long long b[u],c[u],f[u];
long long n,m,t,i,j,x,y;

long long calc(long long a[u],int n)
{
    long long ans=0; int i;
    for(i=1;i<=n;i++)
    {
        a[i]-=a[0]/n;
        f[i]=f[i-1]+a[i];
    }
    sort(f+1,f+n+1);
    for(i=1;i<=n;i++) ans+=abs(f[i]-f[n+1>>1]);
    return ans;
}

int main()
{
    freopen("tanabata.in","r",stdin);
    freopen("tanabata.out","w",stdout); 
    cin>>n>>m>>t;
    for(i=1;i<=t;i++)
    {
        scanf("%d%d",&x,&y);
        b[x]++,c[y]++; 
    }
    for(i=1;i<=n;i++) b[0]+=b[i];
    for(i=1;i<=m;i++) c[0]+=c[i];
    if(b[0]%n==0&&c[0]%m==0)
        printf("both %lld\n",calc(b,n)+calc(c,m));
    else if(b[0]%n==0)
        printf("row %lld\n",calc(b,n));
    else if(c[0]%m==0)
        printf("column %lld\n",calc(c,m));
    else puts("impossible");
    return 0;
}

蒟蒻我的繁杂代码

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
#define ll long long
ll n,m,t,i,j,k,s[N],a[N],x,y,ans1,ans2,r[N],c[N],rr,cc;
void init()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    for (i=1;i<=t;i++)
    {
        int x,y;
        cin>>x>>y;
        r[x]++;
        c[y]++;
        rr++;
        cc++;
    } 
}
bool work1()//横排
{
    if (t%n!=0)
        return 0;
    memset(s,0,sizeof(s));
    rr/=n;
    for (i=1;i<=n;i++)
    {
        r[i]-=rr;
        s[i]=s[i-1]+r[i];
    }
    sort(s+1,s+1+n);
    int k=(1+n)>>1;
    for (i=1;i<=n;i++)
        ans1+=abs(s[i]-s[k]);
    return 1;
}
bool work2()//竖排
{
    if (t%m!=0)
        return 0;
    memset(s,0,sizeof(s));
    cc/=m;
    for (i=1;i<=m;i++)
    {
        c[i]-=cc;
        s[i]=s[i-1]+c[i];
    }
    sort(s+1,s+1+m);
    int k=(1+m)>>1;
    for (i=1;i<=m;i++)
        ans2+=abs(s[i]-s[k]);
    return 1;
}
int main()
{
    init();
    bool ok1=work1(),ok2=work2();
    if (ok1 && ok2)
        cout<<"both";
    else
    if (ok1)
        cout<<"row";
    else if (ok2)
        cout<<"column";
    else 
        cout<<"impossible";
    if (ok1 || ok2)
        cout<<" "<<ans1+ans2;
    return 0;
}