算法

环形平分+前缀和+中位数

我觉得本题的核心在于看出问题可以拆分为行、列独立的环形纸牌平分问题，就结束了（我就没看出来）。

时间复杂度

$O(nlogn)$，复杂度在排序上

参考文献

lyd书

C++ 代码

#include <algorithm>
#include <bits/stdc++.h>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#define oj
using namespace std;

const long long maxn = 1e5 + 10;

long long col[maxn], row[maxn];
long long a[maxn];
long long tem[maxn];

int main()
{
    #ifndef oj
    freopen("data.in", "r", stdin);
    freopen("oj.out", "w", stdout);
#endif
    long long n, m, t;
    cin >> n >> m >> t;
    memset(row, 0, sizeof row);
    memset(col, 0, sizeof col);
    for (long long i = 0; i < t; i++)
    {
        long long x, y;
        scanf("%lld%lld", &x, &y);
        col[y]++, row[x]++;
    }

    bool xf = (t % n), yf = (t % m);
    long long ans = 0;
    if (!xf)
    {
        memset(a, 0, sizeof a);
        long long av = t / n;
        for (long long i = 1; i <= n; i++)
        {
            a[i] = a[i - 1] + row[i] - av;
            tem[i] = a[i];
        }
        sort(tem + 1, tem + 1 + n);
        long long mid = (n & 1) ? tem[(n + 1) >> 1] : tem[n >> 1];
        for (long long i = 1; i <= n; i++)
        {
            ans += abs(a[i] - mid);
        }
    }
    if(!yf){
        long long av = t / m;
        for (long long i=1; i<=m; i++) {
            a[i] = a[i - 1] + col[i] - av;
            tem[i] = a[i];
        }
        sort(tem + 1, tem + 1 + m);
        long long mid = (m & 1) ? tem[(m + 1) >> 1] : tem[m >> 1];
        for (long long i=1; i<=m; i++) {
            ans += abs(a[i] - mid);
        }
    }
    if(!xf&&!yf){
        cout << "both " << ans << endl;
    }else {
    if(!xf)
        cout << "row " << ans << endl;
    else
        if(!yf)
        cout << "column " << ans << endl;
        else {
            cout << "impossible\n";
        }
    }
    return 0;
}