NOIP 2013提高组积木大赛（洛谷P1969）题解：贪心算法优化与代码解析

一、题目解读

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