洛谷P7115 [NOIP2020] 移球游戏题解

题目链接：P7115 [NOIP2020] 移球游戏

题意：

小 C 正在玩一个移球游戏，他面前有 \(n + 1\) 根柱子，柱子从 \(1 \sim n + 1\) 编号，其中 \(1\) 号柱子、\(2\) 号柱子、……、\(n\) 号柱子上各有 \(m\) 个球，它们自底向上放置在柱子上，\(n + 1\) 号柱子上初始时没有球。这 \(n \times m\) 个球共有 \(n\) 种颜色，每种颜色的球各 \(m\) 个。

初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。

小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 \(x\) 号柱子上的球移动到 \(y\) 号柱子上的要求为：

\(x\) 号柱子上至少有一个球；

\(y\) 号柱子上至多有 \(m - 1\) 个球；

只能将 \(x\) 号柱子最上方的球移到 \(y\) 号柱子的最上方。

小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 \(820000\)。换句话说，小 C 需要使用至多 \(820000\) 次操作完成目标。

小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。

输入格式：

第一行两个用空格分隔的整数 \(n, m\)。分别表示球的颜色数、每种颜色球的个数。

接下来 \(n\) 行每行 \(m\) 个用单个空格分隔的整数，第 \(i\) 行的整数按自底向上的顺序依次给出了 \(i\) 号柱子上的球的颜色。

输出格式：

本题采用自定义校验器（special judge）评测。

你的输出的第一行应该仅包含单个整数 \(k\)，表示你的方案的操作次数。你应保证 \(0 \le k \le 820000\)。

接下来 \(k\) 行每行你应输出两个用单个空格分隔的正整数 \(x, y\)，表示这次操作将 \(x\) 号柱子最上方的球移动到 \(y\) 号柱子最上方。你应保证 \(1 \le x, y \le n + 1\) 且 \(x \ne y\)。

数据范围：

保证 \(2 \le n \le 50\)，\(2 \le m \le 400\)。

考虑 \(n=2\) 的情况怎么做。设第一根柱子上有 \(c\) 个 \(1\) ，以及 \(m-c\) 个 \(2\) 。

考虑以下方案：（如果看不懂可以看一下参考文献1的图）

将第二根柱子（没错，就是第二根柱子）最上面的 \(c\) 个球放到第三个柱子上
将第一根柱子上的所有 \(1\) 放到第二根柱子上，其余的放到第三根柱子上

此时第二根柱子有 \((m-c)+c\) 个球，第三根柱子有 \(c+(m-c)\) 个球
然后把第二根柱子上的 \(c\) 个 \(1\) 放到第一根柱子上，再把第三根柱子的 \(m-c\) 个 \(2\) 放到第一根柱子上
接着把第二根柱子剩余的 \(m-c\) 个球放到第三根柱子上
再把第一根柱子的 \(m-c\) 个 \(2\) 放到第二根柱子上
此时我们只需要将第三根柱子上的球按 \(1,2\) 分配到第一、二根柱子上，就完成了。
操作数 \(c + m + m + (m-c) + (m - c) + m = 5m - c\) 。

接着考虑 \(n > 2\) 的情况。

如果我们钦定一个 \(x\) ，把小于等于 \(x\) 的数看作 \(1\) ，大于 \(x\) 的数看作 \(2\) 。

那么一次操作后，相当于把所有小于等于 \(x\) 的都放到了一侧，其余的在另一侧。

考虑分治的解决问题，此时 \(x\) 取区间中点 \(\left\lfloor\frac{l + r}{2}\right\rfloor\) 显然是最优的。

我们将位于左右两侧的 \(i,j\) 一一配对，由于操作数和 \(c\) 有关，所以我们选择选择 \(c\) 较大的那个操作。

这样总操作次数为 \[ \begin{aligned} f(n) &= 2\cdot f\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 5mn \\[6pt] &= \Theta(5mn\log n) \end{aligned} \] 时间复杂度为 \[ \begin{aligned} T(n) &= 2\cdot T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + \frac{n^2m}{4} \\[6pt] &= \Theta(n^2m) \end{aligned} \] 代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll; 
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(55))
#define M ((int)(444))
#define L ((int)(1e6 + 15))

bool vis[N];
int n, m, res, top[N], a[N][M], ans[L][2];
void move(int x, int y)
{
    ++res; ans[res][0] = x, ans[res][1] = y;
    a[y][++top[y]] = a[x][top[x]--];
}
void solve(int l, int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1; memset(vis, 0, sizeof(vis));
    rep(i, l, mid) rep(j, mid + 1, r)
    {
        if(vis[i] || vis[j]) continue;
        int cnt = 0;
        rep(k, 1, m) cnt += (a[i][k] <= mid);
        rep(k, 1, m) cnt += (a[j][k] <= mid);
        if(cnt >= m)
        {
            cnt = 0; rep(k, 1, m) cnt += (a[i][k] <= mid);
            rep(k, 1, cnt) move(j, n + 1);
            while(top[i]) { 
                if(a[i][top[i]] <= mid) move(i, j);
                else move(i, n + 1);
            }
            rep(k, 1, cnt) move(j, i);
            rep(k, 1, m - cnt) move(n + 1, i);
            rep(k, 1, m - cnt) move(j, n + 1);
            rep(k, 1, m - cnt) move(i, j);
            while(top[n + 1]) { 
                if(top[i] == m || a[n + 1][top[n + 1]] > mid) move(n + 1, j); 
                else move(n + 1, i);
            }
            vis[i] = true;
        }else
        {
            cnt = 0; rep(k, 1, m) cnt += (a[j][k] > mid);
            rep(k, 1, cnt) move(i, n + 1);
            while(top[j]) { 
                if(a[j][top[j]] > mid) move(j, i);
                else move(j, n + 1);
            }
            rep(k, 1, cnt) move(i, j);
            rep(k, 1, m - cnt) move(n + 1, j);
            rep(k, 1, m - cnt) move(i, n + 1);
            rep(k, 1, m - cnt) move(j, i);
            while(top[n + 1]) {
                if(top[j] == m || a[n + 1][top[n + 1]] <= mid) move(n + 1, i);
                else move(n + 1, j);
            }
            vis[j] = true;
        }
    }
    solve(l, mid); solve(mid + 1, r);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; int x; 
    rep(i, 1, n) rep(j, 1, m) { cin >> x; a[i][++top[i]] = x; }
    solve(1, n); cout << res << '\n';
    rep(i, 1, res) cout << ans[i][0] << ' ' << ans[i][1] << '\n';
    return 0;
}