Overview

We are given the heights of \(N\) plots lined up in a straight line. We can repeatedly perform an operation to increase the height of each plot by \(1\). The goal is to find the minimum number of operations to eliminate all “valleys” (plots that are strictly lower than both their left and right neighbors).

Analysis

First, to eliminate a valley at plot \(i\), we have no choice but to increase its height \(H_i\). The condition for being a valley is “\(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)”. To make this condition no longer hold, we need to make \(H_i\) at least \(H_{i-1}\) or at least \(H_{i+1}\).

To minimize the number of operations, it is optimal to raise \(H_i\) to the minimum of \(H_{i-1}\) and \(H_{i+1}\) (i.e., \(\min(H_{i-1}, H_{i+1})\)). This ensures that \(H_i\) becomes greater than or equal to at least one of its adjacent plots, meaning it no longer satisfies the valley condition (being strictly smaller than both).

A potential concern here is: “Will raising \(H_i\) create a new valley in another plot?” Specifically, the condition for the right neighbor \(i+1\) to become a valley is “\(H_i > H_{i+1}\) and \(H_{i+1} < H_{i+2}\)”. If we raise \(H_i\) up to \(\min(H_{i-1}, H_{i+1})\), then \(H_i = \min(H_{i-1}, H_{i+1}) \leq H_{i+1}\) holds. Therefore, \(H_i > H_{i+1}\) can never happen.

This shows that a greedy approach—”iterate through the plots from left to right, and if a plot is a valley, raise its height to the minimum of its left and right neighbors”—can resolve all valleys without creating any new ones to the right. Since we never need to backtrack, the process completes in a single pass.

Algorithm

1. If \(N \leq 2\), no valley can exist, so output 0 and terminate.
2. Loop from left to right with \(i = 1\) to \(N-2\) (assuming 0-indexed).
3. If \(H_{i-1} > H_i\) and \(H_i < H_{i+1}\), then plot \(i\) is a valley.
4. Determine the target height target as \(\min(H_{i-1}, H_{i+1})\).
5. Add target - H_i to ans, and update the current height \(H_i\) to target.
6. After the loop ends, output ans.

Complexity

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

Implementation Details

• When processing from left to right, it is crucial to actually update the elements of array \(H\). This ensures that when evaluating the next plot, you use its correct height after the preceding plot has been modified.

• In Python, you can expect a slight speedup by either using the built-in min function or using a ternary operator like H[i - 1] if H[i - 1] < H[i + 1] else H[i + 1].

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    if N <= 2:
        print(0)
        return
    H = list(map(int, input().split()))
    ans = 0
    for i in range(1, N - 1):
        if H[i - 1] > H[i] and H[i] < H[i + 1]:
            target = H[i - 1] if H[i - 1] < H[i + 1] else H[i + 1]
            ans += target - H[i]
            H[i] = target
    print(ans)

if __name__ == '__main__':
    solve()

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