Overview

Given \(N\) flower beds, the problem asks for the minimum number of flowers to add so that the difference in the number of flowers between any two adjacent flower beds is at most \(K\). Flowers cannot be removed; only adding flowers is allowed.

Analysis

The condition for a beautiful flower bed arrangement is that \(|A_i - A_{i+1}| \leq K\) holds for all \(i\). Removing the absolute value, this condition can be decomposed into the following two inequalities:

1. \(A_{i+1} \geq A_i - K\) (the right flower bed is not extremely fewer than the left)
2. \(A_i \geq A_{i+1} - K\) (the left flower bed is not extremely fewer than the right)

Due to the constraint that flowers “cannot be removed (only added),” when the condition is not satisfied, the optimal strategy is to add flowers to the flower bed with fewer flowers so that the difference becomes exactly \(K\).

For example, consider the case \(A = [10, 1], K = 2\). Scanning from left to right, \(A_2\) needs to be at least \(A_1 - K = 8\). Therefore, we update \(A_2\) to \(8\). Conversely, for \(A = [1, 10], K = 2\), scanning from right to left, \(A_1\) needs to be at least \(A_2 - K = 8\).

In this way, by sequentially updating to satisfy condition 1 with a “left-to-right scan” and condition 2 with a “right-to-left scan,” we can satisfy the overall condition with the minimum number of added flowers.

Algorithm

1. Prepare an array \(b\) to manage the current number of flowers (initialized to \(A\)).
2. Forward scan (left to right): For \(i = 1\) to \(N-1\) in order, if \(b[i] < b[i-1] - K\), update \(b[i] = b[i-1] - K\).
3. Backward scan (right to left): For \(i = N-2\) down to \(0\), if \(b[i] < b[i+1] - K\), update \(b[i] = b[i+1] - K\).
4. The answer is the total sum of the final array \(b\) minus the total sum of the original array \(A\).

Complexity

• Time complexity: \(O(N)\) Since we only scan the array once from front to back and once from back to front, the computation finishes in linear time with respect to the number of elements \(N\). This is sufficiently fast even for \(N = 2 \times 10^5\).
• Space complexity: \(O(N)\) This depends on the size of the array used to store the number of flowers.

Implementation Notes

• Computing the total sum: Since the answer can be very large (up to approximately \(N \times 10^9 \approx 2 \times 10^{14}\)), depending on the language, you may need to use a 64-bit integer type (in Python, this is handled automatically).

• Two scans: A single scan alone cannot handle cases where an updated value needs to further update its neighboring value (cascading updates). Scanning from both directions is always necessary.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、スペースで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 花壇の数, K: 許容される花の本数の差
    n = int(input_data[0])
    k = int(input_data[1])
    
    # a: 各花壇の現在の花の本数
    # map関数を使用して一括で整数に変換することで効率化します
    a = list(map(int, input_data[2:]))
    
    # b: 最終的な花の本数を格納するリスト
    # 最初は現在の本数 a で初期化します
    b = list(a)
    
    # 前方向への走査:
    # すべての i について b[i] >= b[i-1] - k を満たすように調整します
    # これにより、b[i-1] - b[i] <= k が保証されます
    for i in range(1, n):
        target = b[i-1] - k
        if b[i] < target:
            b[i] = target
            
    # 後ろ方向への走査:
    # すべての i について b[i] >= b[i+1] - k を満たすように調整します
    # これにより、b[i+1] - b[i] <= k が保証されます
    # 前方向の走査の結果を維持しつつ調整することで、最終的にすべての隣り合う差が K 以下になります
    for i in range(n-2, -1, -1):
        target = b[i+1] - k
        if b[i] < target:
            b[i] = target
    
    # 追加が必要な花の最小本数は、調整後の総本数から元の総本数を引いたものです
    # Pythonの整数型は自動的に多倍長整数として扱われるため、大きな値でも溢れることはありません
    print(sum(b) - sum(a))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.