Overview

This problem asks for the minimum number of snow shoveling operations needed to reduce the snow amount in each section of a road to 0 or below. In one operation, you can reduce the snow by 1 centimeter across any contiguous interval.

Analysis

A naive approach would be to reduce snow sequentially from the beginning. However, processing each section individually would be inefficient since \(N\) can be as large as 200,000.

The key observation is that operations are performed on contiguous intervals. For example, if both sections \(i\) and \(i+1\) have snow, a single operation can reduce both simultaneously. From this property, we can see that “processing adjacent sections together” is efficient for minimizing the number of operations.

Specifically, we scan from the beginning and compare the height that can be covered by current operations (current) with the actual snow height (\(A_i\)). If \(A_i\) is greater than current, additional operations equal to the difference are needed.

Algorithm

The following greedy algorithm is used:

1. Initialization: answer ans=0, height reducible by current operations current=0
2. Process each section i=0 to n-1 in order:
   • If current < \(A_i\), add the difference (\(A_i\) - current) to ans
   • Update current to \(A_i\)
3. Output ans

This method naturally captures the effect of processing contiguous intervals together. current represents “the height already reduced by previous operations,” and we determine that new operations are only needed for the portion where \(A_i\) exceeds current.

Complexity

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

Implementation Notes

• Input reading is optimized by bulk processing with sys.stdin.read()

• It is important to properly update the variable current that maintains the current height

• Since we only need to consider the relationship between adjacent sections, this can be implemented with a simple loop

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    ans = 0
    current = 0
    for i in range(n):
        if current < A[i]:
            ans += A[i] - current
        current = A[i]
        
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.