题目如题

idea

时间复杂度 $O(nlogn + mlogm)$

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, m, t, r[N], c[N], s[N];

LL calc(int a[], int n) {
    memset(s, 0, sizeof s);
    // ∑| s[i] - i * t / n | 转化成 ∑| s[i] | (1 <= i <= n)
    // 此时，可以看成无环均分元素的问题
    for(int i = 1; i <= n; i++) {
        a[i] -= t / n;
        s[i] = s[i - 1] + a[i];
    }
    // ∑| s[i] |转化成∑| s[i] - s[k] | s[k]为s[n]的中位数 (1 <= i <= n)
    // 此时，无环均分元素的问题转化成有环均分元素的问题
    // ans从迭代非0前缀和的次数转化成求最短距的问题
    sort(s + 1, s + 1 + n);
    LL ans = 0;
    for(int i = 1; i <= n; i++) 
        ans += abs(s[i] - s[(n + 1) >> 1]);
    return ans;
}

int main() {
    cin >> n >> m >> t;
    for(int i = 1, x, y; i <= t; i++) { 
        cin >> x >> y;   // 输入cl感兴趣的摊位坐标
        r[x]++, c[y]++;  // 映射摊位数到行与列上 
    }
    int u = t % n, v = t % m; // cl感兴趣的摊位数要能均分到行与列上。必须是行数列数的倍数
    if(!u && !v) cout << "both " << calc(r, n) + calc(c, m) << endl;
    else if(!u) cout << "row " << calc(r, n) << endl;
    else if(!v) cout << "column " << calc(c, m) << endl;
    else cout << "impossible" << endl;
    return 0;
}