题目描述

将题目所给条件抽象成均分纸牌问题，最后转化为货仓选址问题解决。

算法

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e5+10;
int n,m,t;
int row[N],col[N];//按行和按列分块，行交换不影响列的结果，同理列交换不影响行的结果，因此行列分开考虑

long long minstep(int a[],int n)//计算最小交换数
{
    long long res=0,sum=0;
    for(int i=1;i<=n;i++) sum+=a[i];//计算总数
    int avg=sum/n;//平均数，即最终应该达到的状态
    for(int i=1;i<=n;i++) a[i]=a[i-1]+a[i]-avg;//计算每个元素减去平均值后的前缀和
    sort(a+1,a+n+1);//排序方便找出中位数
    for(int i=1;i<=n;i++) res+=abs(a[i]-a[(n+1)/2]);//货仓选址问题，距离总和最小位置在最中间的一条线段中的任何位置，可以认为是两个端点
    return res;
}

int main()
{
    cin>>n>>m>>t;
    for(int i=0;i<t;i++)
    {
        int x,y;
        cin>>x>>y;
        row[x]++;
        col[y]++;
    }//将每一行和每一列的所求元素存入对应的行列

    //有解当且仅当行元素总数或列元素总数可以整除行数或列数（可以均分）
    if(t%n==0 && t%m==0) cout<<"both"<<" "<<minstep(row,n)+minstep(col,m)<<endl;
    else if(t%n==0) cout<<"row"<<" "<<minstep(row,n)<<endl;
    else if(t%m==0) cout<<"column"<<" "<<minstep(col,m)<<endl;
    else cout<<"impossible"<<endl;

    return 0;
}