CSP-S 暑假集训：台阶增高问题

瑜瑜也在ty校园中进行暑假集训，准备冲刺CSP - S一等！他非常的珍惜时间，把所有时间都投入到学习中。而他的机房在科技楼的三楼，每天都要爬弯弯曲曲的楼梯，先到二楼，才能抵达三楼，这使得他非常的烦恼，因为这样会浪费他宝贵的学习时间。

于是他找来了n个台阶，准备搭建一个直达三楼的楼梯！这n块台阶已经摆好，现在已经不能移动了，其中第i块台阶的高度为a_i米。

但是由于估算失误，导致台阶的高度并不是按从小到大的顺序摆放的，于是瑜瑜想对其中一些台阶进行加高处理。加高的规则如下：

对于第i块台阶，如果其高度a_i比前面的某个台阶要低，那么就将台阶的高度增加1米，直到台阶i不比前面的所有台阶更低为止。

瑜瑜想知道，他总共需要对所有的台阶增加多少米，请你帮助他。

C++ 代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> heights(n);

    for (int i = 0; i < n; i++) {
        cin >> heights[i];
    }

    int totalIncrease = 0;
    int maxHeight = heights[0];

    for (int i = 1; i < n; i++) {
        if (heights[i] < maxHeight) {
            totalIncrease += maxHeight - heights[i];
        } else {
            maxHeight = heights[i];
        }
    }

    cout << totalIncrease << endl;

    return 0;
}

解题思路：

首先，我们定义一个变量totalIncrease来记录总共需要增加的高度，初始值为0。

然后，我们定义一个变量maxHeight来记录当前最高的台阶高度，初始值为第一个台阶的高度heights[0]。

接下来，我们从第二个台阶开始遍历，如果当前台阶的高度小于maxHeight，说明需要对当前台阶进行增高。

我们将totalIncrease增加maxHeight减去当前台阶的高度，表示增加的高度。

然后，我们更新maxHeight为当前台阶的高度，继续遍历下一个台阶。

最后，输出totalIncrease表示总共需要增加的高度。

时间复杂度分析：

该算法只遍历了一次台阶，所以时间复杂度为O(n)，其中n为台阶的数量。