【萌新题解】移球游戏

靠一下双指针就能轻松通过,就是分治算法解决柱子排序问题，还是很水的。

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>pir;
vector<int>st[55];
std::vector<pir> ans;
int n, m;
void add(int x, int y, int cnt) {
    // cout << cnt << '\n';
    while (cnt--) {
        st[y].push_back(st[x].back());
        st[x].pop_back();
        // cout << "x=" << x << " y=" << y << '\n';
        if (st[y].size() > m) {
            // exit(0);
            // assert(st[y].size() <= m);
            // cout << "lastx=" << x << " " << y << '\n';
        }
        assert(st[x].size() >= 0);
        ans.push_back({x, y});
    }
}
int spj;
std::vector<pir> spj_st;
// 考虑把 [1,mid]这个值域的数当成 0 ，把 [mid+1,r] 这个值域的数当成 1
// 目标通过洗牌把 1 变到最上面，最终操作时就是把所有的 1 按顺序放到 mid+1,r 中，把 0 放到 l,mid 中
int cnt1[55], cnt0[55];
void divide_conquer(int l, int r) {
    if (l >= r)return;
    int mid = l + r >> 1;
    for (int i = l; i <= r; i++) {
        cnt1[i] = cnt0[i] = 0;
        for (int x : st[i]) {
            if (x > mid)cnt1[i]++;
            else cnt0[i]++;
        }
    }

    // 对于 [l,mid] 中每个柱子 都让 1 在上面 ， 0 在下面
    for (int i = l; i <= mid; i++) {
        int j = i + 1;
        if (i == n)j = i - 1;
        int last = -1;
        for (int k = 0; k < st[i].size(); k++) {
            if (st[i][k] > mid) {
                last = k;
                break;
            }
        }
        if (last == -1)continue;
        // cout << "i=" << i << " " << j << " " << spj << " " << cnt1[i] << " " << cnt0[i] << '\n';
        add(j, spj, cnt1[i]);
        for (int k = st[i].size() - 1; k >= last; k--) {
            if (st[i][k] > mid)add(i, j, 1);
            else add(i, spj, 1);
        }
        int sz = m - last;
        add(spj, i, sz - cnt1[i]);
        add(j, i, cnt1[i]);
        add(spj, j, cnt1[i]);
    }
    // 对于 [mid+1,r] 中每个柱子 都让 0 在上面 ， 1 在下面
    for (int i = mid + 1; i <= r; i++) {
        int j = i + 1;
        if (i == n)j = i - 1;
        int last = -1;
        for (int k = 0; k < st[i].size(); k++) {
            if (st[i][k] <= mid) {
                last = k;
                break;
            }
        }
        if (last == -1)continue;
        add(j, spj, cnt0[i]);
        for (int k = st[i].size() - 1; k >= last; k--) {
            if (st[i][k] > mid)add(i, spj, 1);
            else add(i, j, 1);
        }
        int sz = m - last;
        add(spj, i, sz - cnt0[i]);
        add(j, i, cnt0[i]);
        add(spj, j, cnt0[i]);
    }

    for (int i = l; i <= mid; i++) {
        if (cnt1[i] == 0)continue;
        for (int j = r; j >= mid+1; j--) {
            if (cnt0[j] == 0)continue;
            // i 中 的 1 和 j 中的 0 交换
            if (cnt1[i] > cnt0[j]) {
                add(i, spj, cnt1[i]);
                add(j, i, cnt0[j]);
                add(spj, j, cnt0[j]);
                add(spj, i, cnt1[i] - cnt0[j]);
                cnt1[i] -= cnt0[j];
                cnt0[j] = 0;
            } else {
                add(j, spj, cnt0[j]);
                add(i, j, cnt1[i]);
                add(spj, i, cnt1[i]);
                add(spj, j, cnt0[j] - cnt1[i]);
                cnt0[j] -= cnt1[i];
                cnt1[i] = 0;
            }
        }
    }
    // 递归处理 l,mid
    divide_conquer(l, mid);
    // 递归处理 mid+1,r
    divide_conquer(mid + 1, r);
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            st[i].push_back(x);
        }
    }
    spj = n + 1;
    divide_conquer(1, n);
    cout << ans.size() << '\n';
    for (auto [x, y] : ans)cout << x << " " << y << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("string22.in", "r", stdin);
    // freopen("my.out", "w", stdout);
    solve();
}
/*
考虑把 [1,mid]这个值域的数当成 0 ，把 [mid+1,r] 这个值域的数当成 1
目标通过洗牌把 1 变到最上面，最终操作时就是把所有的 1 按顺序放到 mid+1,r 中，把 0 放到 l,mid 中
*/