03-16 20:46 已编辑牛客小学算法工程师发布于重庆

关注

题解 | # 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;
}

题目二：https://www.luogu.com.cn/problem/P2512

这是均分纸牌的升级版，现在看均分纸牌：是一条链，而不是环，从第一个位置推到最后一个位置即可：

#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;

void solve(){
    
    int n; cin >> n;
    vector<int> a(n + 10);
    int ave = 0;
    for(int i = 1; i <= n; i ++) cin >> a[i], ave += a[i];
    ave /= n;
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        if(a[i] != ave){
            ans ++;
            a[i + 1] += a[i] - ave;
        }
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

而升级版是一个环，可以任意的一个方向：

规定 $i$ 向 $i-1$ 传递 $x$ ，记为 $i-1$ 向 $i$ 传递 $-x$ ，那么整个传递过程就变成单向的传递过程

设 $x_{i}$ 表示 $i$ 向 $i+1$ 传递，特别的， $n$ 传向于 $1$ ，那么：

例如对于第 $1$ 个位置来说， $a_{1}-\bar{a}=x_{n}-x_{1}$ ，意思是我将 $a_{1}$ 修改为 $\bar{a}$ 的值等于第 $n$ 个位置向第一个位置传递的值减去第一个位置向第二个位置传递的值

所以有：

$a_{1}-\bar{a}=x_{n}-x_{1}$

$a_{2}-\bar{a}=x_{1}-x_{2}$

$a_{3}-\bar{a}=x_{2}-x_{3}$

......

$a_{n}-\bar{a}=x_{n-1}-x_{n}$

那么累加前面 $i$ 项可以得到： $\sum_{j=1}^{i}{a_{j}}-i\times \bar{a}$ ，所以 $\sum_{j=1}^{i}{a_{j}}-i\times \bar{a}$ ，直白点是 $\sum_{j=1}^{i}{a_{j}}-i\times \bar{a}$

求 $\sum_{i=1}^{n}{x_{i}}=\sum_{i=1}^{n}{ \left| x_{n} - (\sum_{j=1}^{i}{a_{j}}-i \times \bar{a}) \right| }$ 的最小值，设 $z_{i} = \sum_{j=1}^{i}{a_{j} - i \times \bar{a}}$ ，则求 $\sum_{i=1}^{n}{ \left| x_{n}- z_{i}\right| }$ 的最小值，由中位数定理可知当 $x_{n}$ 为 $z_{i}$ 的中位数时，取得最小值

总代码：

#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;

void solve(){
    
    int n; cin >> n;
    vector<int> a(n + 10), b(n + 10);
    int ave = 0, sum = 0, ans = 0;
    for(int i = 1; i <= n; i ++) cin >> a[i], ave += a[i];
    ave /= n;
    for(int i = 1; i <= n; i ++){
        sum += a[i];
        b[i] = sum - i * ave; 
    }
    sort(b.begin() + 1, b.begin() + 1 + n);
    for(int i = 1; i <= n; i ++){
        ans += abs(b[(n + 1) / 2] - b[i]);
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}