自动搬运

查看原文

来自洛谷，原作者为

	hensier **

搬运于2025-08-24 22:27:41，当前版本为作者最后更新于2021-01-01 12:10:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目定位

这是一道构造题。

题目的要求是将左侧书架的书经过左侧书架、右侧书架、左手和右手的辗转，最终回到左侧书架并实现从顶到底从薄到厚（即单调递增）。

NOIP2020 移球游戏 与其极为相似，只不过两题区别最大的地方就是是否有个数限制。假如这道 NOIP 题没有球的限制，那么能拿到全分也不是很困难的事情。

思路分析

由于本题中可以借助右侧书架进行辗转，因此在分析后可以发现，进入一侧书架的书籍会按照倒序取出。例如，若把厚度为 $\{1,2,3,5\}$ 的书籍依次放入右侧书架，那么取出的顺序就是 $\{5,3,2,1\}$，但放回另一书架的顺序仍为 $\{1,2,3,5\}$。这符合先进后出的原则，也就是我们熟知的数据结构——栈。

本题以栈为数据结构基础，因此完全可以用 stack 或 vector，甚至 deque 等 STL 容器来存储书籍。这里将以 vector 为例。

为了解决本题，我们可以用两个 vector 容器 $l$ 和 $r$ 分别维护左侧和右侧书架中的书籍厚度，并在初始条件下将书籍全部存入 $l$ 中。

接下来就是思考本题的核心策略。这里所用的策略是：第 $i$ 次循环，将左侧书架的书籍中先找到第 $i$ 薄的书籍。随后把所有在该书籍上方的书籍全部放到右侧书架上。接着，将该书籍存放在右手上，再把刚才放到右侧书架上的书全部通过左手放回到左侧书架上。最后，把右手上的书籍放到右侧书架上。

该策略可以运用右侧书架和右手「中转站」的效果，先将书籍从薄到厚放到右侧，再将其依次放回。

具体地，需要执行 $n$ 次以下步骤：

• 将第 $i$ 薄的书籍上方的书全部通过左手放到右侧书架。
• 将第 $i$ 薄的书籍取下并放在右手。
• 将刚才的所有书籍全部通过左手放回左侧书架。
• 将第 $i$ 薄的书籍放到右侧书架。

最后需要将右侧书架上的书全部放回左侧。

样例分析

我们来分析一下上述策略对样例 $1$ 是如何操作的。

样例输入：

3
2 3 1

（第 $0$ 次操作）初始情况：

左侧书架	右侧书架	左手	右手
$2$
$3$
$1$

（第 $1 \sim 4$ 次操作）将左侧书架 $1$ 上方的所有书籍取出，并放在右侧：

左侧书架	右侧书架	左手	右手
$1$	$3$
	$2$

（第 $5$ 次操作）将 $1$ 取下放在右手（将右侧书籍放回左侧时使用左手）：

左侧书架	右侧书架	左手	右手
	$3$		$1$
	$2$

（第 $6 \sim 9$ 次操作）把 $2$ 和 $3$ 用左手放回左侧：

左侧书架	右侧书架	左手	右手
$2$			$1$
$3$

（第 $10$ 次操作）将 $1$ 放在右侧：

左侧书架	右侧书架	左手	右手
$2$	$1$
$3$

（第 $11 \sim 14$ 次操作）接着，由于中间无其他书籍，将 $2$ 和 $3$ 依次放在右侧：

左侧书架	右侧书架	左手	右手
	$3$
	$2$
	$1$

（第 $15 \sim 20$ 次操作）左侧书架已空，因此可将所有书籍依次放回：

左侧书架	右侧书架	左手	右手
$1$
$2$
$3$

操作次数分析

该策略的最坏情况是所有的 $n$ 本书籍从厚到薄，与题目要求的顺序恰好相反。

在最坏情况之下，对于第 $i$ 薄的书籍，各种操作所需次数为：

• 一堆放至右侧：$2(i-1)$
• 一本放至右手：$1$
• 一堆放回左侧：$2(i-1)$
• 一本放至右侧：$1$
• 总计：$\sum_{i=1}^n (4i-2)$

最后放回左侧和总计次数为 $2n$，所以总次数为：

$$\sum_{i=1}^n (4i-2)+2n=\dfrac{4n(n+1)}{2}-2n+2n=2n(n+1) $$

由于 $n \le 100$，所以总操作次数必定不超过 $20200$，而规定次数为 $100000$，可以稳过。

代码 1

用 vector 模拟书架。

#include<bits/stdc++.h>
using namespace std;
int n,cnt,a[101];
string op[100001];
vector<int>l,r;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=n;i;--i)l.push_back(a[i]);
    sort(a+1,a+n+1);
    for(int i=1,t;i<=n;++i)
    {
        t=0;//t 将保存需要取下书籍数目
        //将第 i 薄的书籍上方的全部移至右侧
        while(l.back()!=a[i])
        {
            op[++cnt]="UZMI L L\n";
            op[++cnt]="STAVI L D\n";
            r.push_back(l.back());
            l.pop_back();
            ++t;
        }
        //将第 i 薄的书籍暂时存放在右手
        op[++cnt]="UZMI D L\n";
        l.pop_back();
        //将刚才移动的书籍全部放回左侧书架
        while(t--)
        {
            op[++cnt]="UZMI L D\n";
            op[++cnt]="STAVI L L\n";
            l.push_back(r.back());
            r.pop_back();
        }
        //把存在右手的第 i 薄书籍放回右侧书架
        op[++cnt]="STAVI D D\n";
        r.push_back(a[i]);
    }
    //把右侧书架上剩余的书籍全部放至左侧书架顶端
    while(r.size())
    {
        op[++cnt]="UZMI L D\n";
        op[++cnt]="STAVI L L\n";
        l.push_back(r.back());
        r.pop_back();
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;++i)cout<<op[i];
    return 0;
}

代码 2

不使用 vector 来浪费太多空间。我们可用数组维护每本书籍的高度（最顶端为 $1$，最底端为 $n$）。

在对书籍厚度排序之后，每次移动之后都相应改变高度，并保存输出结果。

本代码复杂度虽与前者相当，都是 $\mathcal O(n^2)$。但前者内层循环的 $n$ 是跑不满的，而该代码是无论如何都要跑的，所以速度较慢。不过，该代码在空间略胜于前者。

#include<bits/stdc++.h>
int n,cnt;
char ans[1000001];//保存输出结果
struct book
{
    int width,id;
    bool operator<(const book &x) const {return width<x.width;}
}a[101];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i].width);//输入厚度（可以理解为宽度）
        a[i].id=i;//保存初始高度
    }
    std::sort(a+1,a+n+1);//从薄到厚进行排序
    for(int i=1;i<=n;++i)
    {
        //将上方所有书籍进行移动，strcat 可拼接字符数组
        for(int j=0;j<a[i].id-1;++j)strcat(ans,"UZMI L L\nSTAVI L D\n");
        strcat(ans,"UZMI D L\n");
        for(int j=0;j<a[i].id-1;++j)strcat(ans,"UZMI L D\nSTAVI L L\n");
        strcat(ans,"STAVI D D\n");
        cnt+=((a[i].id-1)<<2)+2;//操作次数记录
        for(int j=1;j<=n;++j)//对各本书籍的高度进行修改
        {
            if(a[j].id<=a[i].id)continue;
            --a[j].id;
        }
    }
    printf("%d\n%s",cnt+(n<<1),ans);//操作次数还需加上最后 2n 次
    while(n--)puts("UZMI L D\nSTAVI L L");//输出最后 2n 次操作
    return 0;
}