洛谷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;
}