河外塔问题（简单版） - ZSHOI-R1 - 算法竞赛题解

河外塔问题（简单版） - ZSHOI-R1 - 算法竞赛题解

题目描述：

河外塔问题是河内塔问题的延申，但初始顺序不固定，允许大的圆盘放在小的圆盘上。你需要将 n 个圆盘从柱 A 移动到柱 C，操作次数不超过 10^6 次。

思路：

由于允许大的圆盘放在小的圆盘上，我们可以直接将圆盘从 A 移动到 C，不需要像标准的汉诺塔问题那样严格地按照大小顺序移动。因此，我们可以采取以下策略：

1. 找到 A 上最大的圆盘，将其移动到 C。
2. 将 A 上剩余的圆盘依次移动到 B。
3. 将 C 上最大的圆盘移动到 A。
4. 将 B 上的圆盘依次移动到 C。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int tot = 0;
  // 找到 A 上最大的圆盘
  int max_disk = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] > a[max_disk]) {
      max_disk = i;
    }
  }

  // 将最大的圆盘移动到 C
  cout << "A C" << endl;
  tot++;
  a.erase(a.begin() + max_disk);

  // 将 A 上剩余的圆盘移动到 B
  for (int i = 0; i < a.size(); i++) {
    cout << "A B" << endl;
    tot++;
  }

  // 将 C 上最大的圆盘移动到 A
  cout << "C A" << endl;
  tot++;

  // 将 B 上的圆盘移动到 C
  for (int i = 0; i < a.size(); i++) {
    cout << "B C" << endl;
    tot++;
  }

  cout << tot << endl;
  return 0;
}

测试数据：

样例输入：

3
1 2 3

样例输出：

5
A C
A B
A B
B C
B C

总结：

河外塔问题（简单版）是一道简单易懂的题目，只需要找到 A 上最大的圆盘，将其移动到 C，然后将 A 上剩余的圆盘移动到 B，再将 C 上最大的圆盘移动到 A，最后将 B 上的圆盘移动到 C 即可。