题意：
有三个柱子，n个圆盘按照A排列从上到下排列在第一个柱子上，每次操作可将一个柱子最上面的圆盘移动到另一个柱子上。
要使得这n块圆盘在任意同一柱子上，且从上到下编号递增。
最多操作10^6次，输出每次操作。
分析：
题目没有规定操作次数的具体限制，我们的操作方案甚至可以不是最优的！相同算法操作次数同阶，那么目标柱子的选定也不是那么必要了。
假定3为目标柱子，那么1、2两个柱子作为转移的辅助柱子足够完成任务。
操作比较明晰：
每次将当前柱子（1或2）上的盘子依次移走，如果盘子编号是当前未处理中最大的，则移到3柱，否则移到另一个辅助柱上。
操作次数是n+(n-1)+...+2+1，O（n^2）级别的。
模拟的代码各有各的写法，自己看着清晰最重要了吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | const int N=10000+10;int n,K,a[N],b[N],tot;int main(){ n=read(); F(i,1,n) a[i]=read(); K=n*(1+n)/2;printf("%d\n",K); D(x,n,1){ tot=x; F(i,1,x){ if(a[i]!=x){ b[--tot]=a[i]; if((n-x)%2) puts("2 1"); else puts("1 2"); } else printf("%d 3\n",(n-x)%2?2:1); } swap(a,b); } return 0;} |
评论 (0)
