Overview

This problem asks for the minimum number of operations (each operation increases the height of a section by 1) required to eliminate all sections that are lower than both of their neighbors (pits).

Analysis

First, the condition for section \(i\) to be a pit is “\(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)”. To resolve this, since we cannot decrease heights, we must increase the height of \(H_i\). To eliminate the pit with the minimum increase, we should increase \(H_i\) to the height of its lower neighbor, which is \(\min(H_{i-1}, H_{i+1})\). In this case, the required number of operations is \(\min(H_{i-1}, H_{i+1}) - H_i\).

However, the problem statement contains a note: “As a result of increasing the height of a section, another section might newly satisfy the condition of being a pit.” Let’s verify this. Suppose we increase the height of section \(i\) up to \(\min(H_{i-1}, H_{i+1})\). At this point, \(H_i \le H_{i+1}\) and \(H_i \le H_{i-1}\) will hold (since we only increase it up to equality at most). For a new pit to be created, the condition for the neighboring sections \(i-1\) or \(i+1\) to become pits must be satisfied, i.e., “\(H_{i-2} > H_{i-1} < H_i\)” or “\(H_i > H_{i+1} < H_{i+2}\)”. However, even after increasing \(H_i\), it will never happen that \(H_{i-1} < H_i\) (they are at most equal), and similarly, \(H_i > H_{i+1}\) will never happen. Therefore, as long as we only increase the height up to \(\min(H_{i-1}, H_{i+1})\), the neighboring sections will never newly become pits. In fact, if the neighbors were already pits, increasing \(H_i\) actually helps to resolve those pits.

In conclusion, the pits at each section can be resolved independently of each other. The minimum number of operations can be found simply by summing up \(\min(H_{i-1}, H_{i+1}) - H_i\) for each pit.

Algorithm

1. Receive the height array \(H\) as input.
2. Prepare a variable to store the answer (use a wide type such as long long to prevent overflow).
3. Loop \(i\) from \(1\) to \(N - 2\) (assuming 0-indexed).
4. If \(H[i-1] > H[i]\) and \(H[i] < H[i+1]\), it is a pit, so add \(\min(H[i-1], H[i+1]) - H[i]\) to the answer.
5. Finally, output the answer.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Details

• When \(N \leq 2\), there are no sections other than the two ends. Therefore, the loop range \(1 \leq i \leq N-2\) becomes empty, and 0 is automatically and correctly output.

• Since the upper limits of \(H_i\) and the number of operations can be large, the total sum of the answer may exceed the range of a 32-bit integer (int type). Therefore, in C++, you need to use a type like long long.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    long long ans = 0;
    for (int i = 1; i < N - 1; ++i) {
        if (H[i - 1] > H[i] && H[i] < H[i + 1]) {
            ans += min(H[i - 1], H[i + 1]) - H[i];
        }
    }
    
    cout << ans << "\n";
    return 0;
}

This editorial was generated by or-glm5.2-high.