题解 | # P10453 七夕祭 #

$[思维]$

前提知识：

题目的意思是有一个 $n\times m$ 个摊位，然后给出喜欢的 $t$ 个摊位的左边 $(x_{i},y_{i})$ ，每次操作可以在某一行或某一列里面选取相邻的两个摊位（每一行或每一列的第一个位置和最后一个位置也算作相邻）然后交换这两个摊位，目的是使得每一行的摊位个数相同，每一列的摊位个数相同并且输出最小操作次数，具体输出 $both,column,row,impossible$ ，如果不是 $impossible$ ，则还需要输出最小的操作次数

分析题目可知一个性质：

行与列是独立的，在某一行上交换摊位，那么这一行的喜欢摊位是不会发生变化，而是会改变某两列的喜欢摊位个数；所以答案可以分成两个相互独立的部分计算：通过最少次数的左右交换使每列中的喜欢摊位相同；通过最少次数的上下交换使得每行中的喜欢摊位相同

由均分纸牌可知：

首先摊位的个数 $t$ 要满足均分，则 $t$ 必须是 $n$ 的倍数，才能经行操作使得每一行的摊位数相同， $m$ 同理，这是前提条件
最小操作的次数是 $\sum_{i=1}^{n}{\left| \frac{t}{n} \times i -pre[i] \right|}$ ，其中 $pre[i]=\sum_{j=1}^{i}{r[j]}$ ，如果一开始让每一个 $r[i]$ 都减去 $\frac{t}{n}$ ，设 $A[i]=r[i]-\frac{t}{n}$ ，最小操作次数又等于 $\sum_{i=1}^{n}{\left| S[i] \right|}$ ，其 $S[i]=\sum_{j=1}^{i}{A[j]}$

这相当于环性均分纸牌因为题目中说（每一行或每一列的第一个位置和最后一个位置也算作相邻），朴素的做法是化环为链，枚举每一个分界点 $k$ ， $k\in [1,n]$ ，那么对应的 $S[i]$ 就需要变化了，因为原来默认是在 $k=n$ 与 $1$ 之间断开，讨论的是区间 $[1,n]$ 的答案。

所以 $S[1] = S[k +1]-S[k]$ ， $S[2] = S[k +2]-S[k]$ ，......， $S[n-k] = S[n]-S[k]$ ， $S[n-k+1] = S[1]+S[n]-S[k]$ ，......， $S[k] = S[k]+S[n]-S[k]$

那么答案就是找到一个 $k$ ， $k\in [1,n]$ ，求得 $\sum_{i=1}^{n}{\left| S[i]-S[k] \right|}$ 最小，一看发现是货仓选址找中位数的题目，只需要排序即可，不需要去找 $k$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int N = 100010;
int n, m, t;
int r[N], c[N];
void solve(){

    cin >> n >> m >> t;
    for(int i = 1; i <= t; i ++){
        int x, y; cin >> x >> y;
        r[x] ++, c[y] ++;
    }
    int ans = 0;
    bool ok_row = false, ok_col = false;
    if(t % n == 0){
        ok_row = true;
        int ave = t / n;
        vector<int> pre(n + 1);
        for(int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + r[i] - ave;
        sort(pre.begin() + 1, pre.begin() + 1 + n);
        for(int i = 1; i <= n; i ++) ans += abs(pre[i] - pre[n / 2 + 1]);
    }
    if(t % m == 0){
        ok_col = true;
        int ave = t / m;
        vector<int> pre(m + 1);
        for(int i = 1; i <= m; i ++) pre[i] = pre[i - 1] + c[i] - ave;
        sort(pre.begin() + 1, pre.begin() + 1 + m);
        for(int i = 1; i <= m; i ++) ans += abs(pre[i] - pre[m / 2 + 1]);
    }
    if(ok_row && ok_col) cout << "both" << " " << ans << endl;
    else if(ok_row && !ok_col) cout << "row" << " " << ans << endl;
    else if(!ok_row && ok_col) cout << "column" << " " << ans << endl;
    else cout << "impossible" << endl;
    return ;
}

signed main(){
    HelloWorld;
    
    int tt = 1; 
    while(tt --) solve();
    return 0;
}