算法/复杂度

前导知识，我的解法涉及一个贪心模板 ，请先看透这个题 :糖果传递

核心问题分析：

1. 首先提醒一下，在一行中，各列摊位之间交换位置，是不改变行的摊位数量的。列同理。
2. 我们模拟一下交换的过程：

​ 假设七夕祭有12个摊位，图中有红圈的是题目主角喜欢的摊位。

​ 经过两轮交换后各列的摊位的红圈的数量都一样了，但各行的红圈数量没有发生过变化。

这个题和 糖果传递 那个题有什么关联呢？

别急，我先把这个图改一改（把线擦去了）。

​ 你们看，这些红圈像不像糖果，哈哈哈哈哈哈哈哈，相邻列之间交换摊位，就像是相邻两个小朋友正交换糖果嘛。

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;
ll res1,res2;
int row[N],col[N],tmp[N];

int main()
{
    int n,m,c;
    cin>>n>>m>>c;

    //开始分别记录行列
    for(int i=0,x,y;i<c;i++)
    {
        cin>>x>>y;
        row[x]++;
        col[y]++;
    }


    //计算行的最小交换次数
    if(c%n==0)
    {
        //求平均值
        int rowi = c/n;
        int x1;
        //从1开始，x,y都是大于1的
        for(int i = 2 ; i <= n ; i++)
            tmp[i] = tmp[i-1] + rowi -row[i];
        //排序
        sort(tmp+1,tmp+n+1);
        if(n%2==0) x1 = (tmp[n/2] + tmp[n/2+1])/2;
        else x1 = tmp[n/2];
        //求距离和
        for(int i = 1 ; i <= n  ; i++)
          res1 += abs(x1 - tmp[i]);
    }

    //计算列的最小交换次数
    if(c%m==0)
    {
        //求平均值
        int coli = c/m;
        int  x1=0;
        //从1开始，x,y都是大于1的
        for(int i = 1 ; i <= m ; i++)
            tmp[i] = tmp[i-1] + coli -col[i];
        //排序
        sort(tmp+1,tmp+m+1);
        if(m%2==0) x1 = (tmp[m/2] + tmp[m/2+1])/2;
        else x1 = tmp[m/2];
        //求距离和
        for(int i = 1 ; i <= m  ; i++)
          res2 += abs(x1 - tmp[i]);

    }

    if(res1&&res2) cout<<"both "<<res1+res2;
    else if(res1) cout<<"row "<<res1;
    else if(res2) cout<<"column "<<res2;
    else cout<<"impossible";

    return 0;
}