NOIP 2013提高组积木大赛（洛谷P1969）题解：贪心算法优化与代码解析
2天前
一、题目解读
2013年NOIP提高组“积木大赛”（洛谷P1969）要求处理积木堆叠问题。题目给定n个积木高度，需计算按特定规则堆叠后的总高度差。核心在于识别上升序列的累积增量，而非简单求和。
二、解题思路
观察数据规律后，采用贪心策略：仅统计连续上升的积木高度差。若当前积木高于前一个，则累加差值至结果，避免下降段的无效计算。此思路时间复杂度O(n)，无需复杂数据结构。
三、解题步骤
1. 输入积木数量n及每个高度值。
2. 初始化前值prev、当前值current与答案ans。
3. 循环遍历高度：若current>prev，执行ans += current - prev。
4. 更新prev为当前值，维持上升判断基准。
5. 输出最终答案。
四、代码与注释
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n; // 输入积木数量
int prev = 0, current = 0, ans = 0;
for(int i = 0; i < n; ++i) {
cin >> current; // 读取当前高度
if(current > prev) { // 仅累加上升部分
ans += current - prev;
}
prev = current; // 更新基准值
}
cout << ans << endl;
return 0;
}五、总结
该解法巧妙利用贪心思想，通过局部最优（仅统计上升差）达到全局最优解。代码简洁高效，适用于线性数据场景。注意边界处理（首项默认为0），避免复杂逻辑嵌套。
参考：NOIP
原创内容 转载请注明出处
