1-9 堆宝塔

题目要求：

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小，按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下：

• 首先准备两根柱子，一根 A 柱串宝塔，一根 B 柱用于临时叠放。
• 把第 1 块彩虹圈作为第 1 座宝塔的基座，在 A 柱放好。
• 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下，如果比最上面的小，就直接放上去；否则把 C 跟 B 柱最上面的彩虹圈比一下：
• 如果 B 柱是空的、或者 C 大，就在 B 柱上放好；
• 否则把 A 柱上串好的宝塔取下来作为一件成品；然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上，最后把 C 也放到 A 柱上。

重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？

输入格式：

输入第一行给出一个正整数 N（≤103），为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数，对应每个彩虹圈的直径。

输出格式：

在一行中输出宝宝堆出的宝塔个数，和最高的宝塔的层数。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

2. 11
3. 10 8 9 5 12 11 4 3 1 9 15

复制代码

输出样例：

2. 4 5

复制代码

样例解释：

宝宝堆成的宝塔顺次为：

• 10、8、5
• 12、11、4、3、1
• 9
• 15、9

解题思路：

如此长的题目，其实可以总结为以下几点：

1.初始使用A柱；

2.如果当前圆环比A柱顶部小，则可以直接放上去；

3.否则，如果B柱顶部比当前圆环小，也可以放入B柱；

4.如果两柱都无法放，则视为A柱已构成一个完整宝塔，将A柱的圆环收集后清空；

5.将B柱中比当前圆环大的元素转移到A柱，以尝试继续构建新塔；

6.最后，把剩余的A柱、B柱也分别视为塔加入统计中。

7.最后的最后，再输出宝塔总数和最高宝塔的层数。

代码：

2. #include <iostream>
3. #include <vector>
4. #include <stack>
5. #include <algorithm>
6. using namespace std;
8. int main()
9. {
10. int N;
11. cin >> N;
12. vector<int> rings(N);
13. for (int i = 0; i < N; ++i)
14. {
15. cin >> rings[i];
16. }
18. vector<vector<int> > towers; // 保存每个完整宝塔（记录每层）
20. stack<int> A, B; // A柱和B柱
21. int max_height = 0;
23. for (int i = 0; i < N; ++i)
24. {
25. int C = rings[i];
27. if (A.empty())
28. {
29. A.push(C);
30. }
31. else if (C < A.top())
32. {
33. A.push(C);
34. }
35. else
36. {
37. if (B.empty() || C > B.top())
38. {
39. B.push(C);
40. }
41. else
42. {
43. // A柱成品宝塔完成
44. vector<int> tower;
45. while (!A.empty())
46. {
47. tower.push_back(A.top());
48. A.pop();
49. }
50. max_height = max(max_height, (int)tower.size());
51. towers.push_back(tower);
53. // B柱比C大的移到A柱
54. while (!B.empty() && B.top() > C)
55. {
56. A.push(B.top());
57. B.pop();
58. }
59. A.push(C);
60. }
61. }
62. }
64. // 收尾：A柱宝塔
65. if (!A.empty())
66. {
67. vector<int> tower;
68. while (!A.empty())
69. {
70. tower.push_back(A.top());
71. A.pop();
72. }
73. max_height = max(max_height, (int)tower.size());
74. towers.push_back(tower);
75. }
77. // B柱也成一个塔
78. if (!B.empty())
79. {
80. vector<int> tower;
81. while (!B.empty())
82. {
83. tower.push_back(B.top());
84. B.pop();
85. }
86. max_height = max(max_height, (int)tower.size());
87. towers.push_back(tower);
88. }
90. cout << towers.size() << " " << max_height << endl;
91. return 0;
92. }

复制代码

答题结果：

个人总结：

1.数据结构：根据题目给出的信息，我们不难发现，该题目适合使用栈的结构进行解决，一共需要建立两个栈，分别模拟两个宝塔。

2.思路：对于每个个圆环来说，每个新圆环按照大小关系被有序地放置在A柱或B柱中。如果无法继续放置，则将当前A柱的内容保存为一个完成的宝塔，并清空以重新构建。

3.核心点：该题目的核心在于通过合理地在两个柱子之间转移圆环，实现尽可能多的塔构建，并记录其中最高的塔高度。最本质的算法核心则是贪心算法的思想。

4.语言：最后，再次强调对C++vector容器和stack的正确使用，二维的vector模拟了一个动态的二维数组，而stack提供的pop、top、push等方法则模拟了圆环的拿取和放下，实现了题目的要求。