P7209 [COCI2020-2021#3] Knjige 题解

· · 题解

题目定位

这是一道构造题。

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

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 次以下步骤：

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

样例分析

我们来分析一下上述策略对样例 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 薄的书籍，各种操作所需次数为：

最后放回左侧和总计次数为 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;
}