NOIP 2013 提高组 洛谷P1969题：贪心算法在积木大赛中的神奇应用

一、问题分析

积木大赛问题要求计算将初始全0序列通过区间+1操作变为目标序列所需的最少操作次数。关键在于发现操作之间的包含关系，转化为差分问题求解。

二、C++代码实现

#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;
}

三、算法原理详解

1. 贪心策略：

• 把连续递增的区间看作一个操作单元

• 每个上升段的差值即为需要新增的操作次数

• 时间复杂度O(n)，空间复杂度O(1)

2. 差分思想：

• 实际计算的是目标序列的离散差分

• 正差分值的和即为答案

• 例如序列[2,3,4,1,2]的差分为[+2,+1,+1,-3,+1]

3. 操作模拟：

• 初始：[0,0,0,0,0]

• 操作1：[1,1,1,1,1]（覆盖全部）

• 操作2：[2,2,2,1,1]（前3项）

• 操作3：[2,3,3,1,1]（第2项）

• 操作4：[2,3,4,1,1]（第3项）

• 操作5：[2,3,4,1,2]（最后项）

四、常见错误排查

1. 初始值未设为0导致首项计算错误

2. 使用数组存储全部数据导致空间浪费

3. 未考虑下降序列的特殊情况

4. 整数溢出问题（本题数据范围无需处理）