【UOJ#152】【UR#10】汉诺塔 | Mrsrz's blog

构造

题目大意：

给定三个栈，初始第一个栈中有一个长度为 $n(n\leqslant 10^4)$ 的排列，另外两个栈为空。

一次操作可以把一个栈的栈顶元素移动到另一个栈的栈顶。

要求最多执行 $10^6$ 次操作，使得将所有数移动到同一个栈（任意选择一个），并且满足从栈顶到栈底，数的大小依次递增。

题解：

让你找到一种可行的方案。也算构造题吧。

不难想到我们需要设计一种操作次数为 $O(n\log n)$ 的算法（$O(n\sqrt n)$ 也能过但需要非常优秀的常数）。

可以采用归并排序的办法。每次将待排序列划分成两份，对两边分别排序后，再通过线性的时间进行合并。

这里我们对第一个栈的部分排序时，把一半丢到第二个栈里。对第二个栈的部分排序时，把一半丢到第一个栈里。

假设两个栈的栈顶的一部分元素都有序（从上到下依次递增），此时第三个栈保持空闲。

我们每次选择两个栈的栈顶元素较小的那个，把它放到第三个栈中。

这时第三个栈中的元素从上到下是依次减小的。

那么把它依次弹回第一个或第二个栈中，就从小到大排完了。

算法的时间复杂度是 $O(n\log n)$。这个复杂度的算法并不需要太注意常数。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>A[3];
vector<pair<int,int> >op;
int n;
struct info{
    int id,l,r;
};
info solve(info now){
    if(now.l==now.r)return now;
    const int mid=now.l+now.r>>1;
    int beg=A[now.id^1].size();
    while((int)A[now.id].size()-1!=mid){
        op.emplace_back(now.id,now.id^1);
        A[now.id^1].push_back(A[now.id].back());
        A[now.id].pop_back();
    }
    int ed=(int)A[now.id^1].size()-1;
    info L=solve((info){now.id,now.l,mid}),R=solve((info){now.id^1,beg,ed});
    int be2=A[2].size(),top0=L.r,top1=R.r;
    while(top0>=L.l&&top1>=R.l)
    if(A[now.id][top0]<A[now.id^1][top1]){
        A[2].push_back(A[now.id][top0]);
        A[now.id].pop_back();
        op.emplace_back(now.id,2);
        --top0;
    }else{
        A[2].push_back(A[now.id^1][top1]);
        A[now.id^1].pop_back();
        op.emplace_back(now.id^1,2);
        --top1;
    }
    while(top0>=L.l){
        A[2].push_back(A[now.id][top0]);
        A[now.id].pop_back();
        op.emplace_back(now.id,2);
        --top0;
    }
    while(top1>=R.l){
        A[2].push_back(A[now.id^1][top1]);
        A[now.id^1].pop_back();
        op.emplace_back(now.id^1,2);
        --top1;
    }
    while((int)A[2].size()-1>=be2){
        A[now.id].push_back(A[2].back());
        op.emplace_back(2,now.id);
        A[2].pop_back();
    }
    return now;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        A[0].push_back(x);
    }
    reverse(A[0].begin(),A[0].end());
    solve((info){0,0,n-1});
    cout<<op.size()<<'\n';
    for(auto it:op)
    cout<<it.first+1<<' '<<it.second+1<<'\n';
    return 0;
}