A20230. 能量槽
填空题
困难
知识点
题目描述
能量槽
题目描述
在实验室中，有一个“能量槽”和 n 个待处理的能量块。第i个能量块的能级为ai，其蕴含的能量为2ai。
实验需按顺序执行n次操作，第i次操作流程如下：
（1）将第i个能量块放入堆槽的顶部。
（2）随后启动“自动融合程序”，重复执行以下检查，直到无法继续：
若槽中能量块数量≤1，停止融合。
若顶部第 1 个与第 2 个能量块的能级不同，停止融合。
若顶部两个能量块能级相同，则将它们从槽中移除，并向顶部放入一个能级为原能级 + 1的新能量块，其能量为两者之和。
再次回到检查步骤，继续尝试融合。
求 n 次操作全部完成后，槽中剩余的能量块总数。
输入格式
第一行，一个整数n。
接下来 n 行，每行一个整数 ai。
输出格式
输出 n 次操作结束后槽中剩余能量块的数量。
输入样例#1
7
2
1
1
3
5
3
3输出样例#1
3输入样例#2
5
0
0
0
1
2输出样例#2
4说明提示
1≤n≤2×10^5，0≤ai≤10^9，输入均为整数。
限制
时间限制：1000ms，内存限制：256MiB
参考答案
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
stack<long long> st; // 存储能级，用 long long 防止溢出
while (n--) {
long long x;
cin >> x;
st.push(x);
// 循环合并栈顶两个相同的元素
while (st.size() >= 2) {
// 取出栈顶两个
long long a = st.top(); st.pop();
long long b = st.top(); st.pop();
if (a == b) {
// 相同则合并成 +1 级，重新压入
st.push(a + 1);
} else {
// 不同则放回，停止合并
st.push(b);
st.push(a);
break;
}
}
}
// 最终栈大小就是答案
cout << st.size() << endl;
return 0;
}
上一题
下一题