題目鏈接

題意：

有三根編號為\((1, \, 2, \, 3)\)的柱子，然后第一根柱子上有編號為\(1 \sim n(n \leq 10000)\)的盤子，從上到下第\(i\)個盤子的編號是\(A_i\)，其他兩根柱子是空的。
你可以進行一種操作x y，表示將第\(x\)根柱子最上面的盤子放到第\(y\)根柱子的最上面去。
輸出不超過\(10^6\)次操作，使得最終所有的盤子都在同一根柱子(柱子的編號不限)上而且從上到下編號是遞增的。

分析：

首先很容易想到一個\(O(n^2)\)的做法：
就是每次遇到不是\(n\)的盤子的時候就扔到柱子\(3\)上去，否則就扔到柱子\(2\)上去。
然后重復這一過程，在\(n-1\)號盤子所在的柱子上，遇到不是\(n-1\)的就扔到其他柱子上，遇到\(n-1\)就扔到柱子\(2\)，也就是\(n\)號盤子的上面。

然后有一個\(O(n^{\frac{3}{2}})\)的做法。是基于平方分割的思想，每次取出\(\sqrt{n}\)個編號最大的盤子，然后暴力用\(O((\sqrt{n})^2)=O(n)\)次操作將其排序。

最后是\(O(nlogn)\)的做法：
這種做法是基于分治的思想，和快排的思路一模一樣：先分解問題然后再合并問題。
我們規定從上到下遞增的是順序，從上到下遞減的是逆序。
分：

對于某個柱子上亂序的區間\([l, \, r]\)，如果我們要將它順序排序，我們可以將\([l, \, mid]\)中的盤子和\([mid+1, \, r]\)中的盤子分別扔到其他兩根柱子上。
然后對這兩個根柱子上的盤子逆序排序。

合：

左右區間逆序排好序后然后按照從大到小的順序再放回原來的柱子上，使得整個\([l, \, r]\)是順序的。

對\([l, \, mid]\)和\([mid+1, \, r]\)這兩個區間逆序排序，這樣問題的規模就減小了一半。
相反地，如果要對一個區間逆序排序，就要先對它的左右區間順序排序，然后合并。

#include <cstdio> #include <algorithm> #include <cstring> using namespace std;const int maxn = 10000 + 10; int n; int cnt[3], t[3][maxn]; int lft[] = { 1, 0, 0 }; int rgh[] = { 2, 2, 1 };void op(int i, int j) {printf("%d %d\n", i + 1, j + 1);t[j][cnt[j]] = t[i][cnt[i]-1];cnt[j]++; cnt[i]--; }void solve(int cur, int l, int r, bool inv) {if(l == r) return;int mid = (l + r) / 2;for(int i = 1; i <= r-l+1; i++) {if(t[cur][cnt[cur]-1] <= mid) op(cur, lft[cur]);else op(cur, rgh[cur]);}solve(lft[cur], l, mid, !inv);solve(rgh[cur], mid+1, r, !inv);if(!inv) {for(int i = mid + 1; i <= r; i++) op(rgh[cur], cur);for(int i = l; i <= mid; i++) op(lft[cur], cur);} else {for(int i = l; i <= mid; i++) op(lft[cur], cur);for(int i = mid + 1; i <= r; i++) op(rgh[cur], cur);} }int ans;void dfs(int t) {if(t == 1) return;ans += t * 2;dfs(t / 2);dfs(t - t / 2); }int main() {scanf("%d", &n);cnt[0] = n;for(int i = n-1; i >= 0; i--) scanf("%d", &t[0][i]);ans = 0;dfs(n);printf("%d\n", ans);solve(0, 1, n, false);return 0; }

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/5093026.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的UOJ 152 汉诺塔 分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。