Overview

This problem asks us to place a single sprinkler on a straight flower bed to minimize the number of unwatered flowers. We can find the answer by subtracting the “maximum number of watered flowers” from the “total number of flowers”. We can search for the optimal sprinkler position efficiently using the two-pointer technique.

Analysis

According to the problem description, when a sprinkler is placed at coordinate \(s\), it can water the flowers in the plants that satisfy \(s \leq X_i < s + D\). Since we want to minimize the number of unwatered flowers, this can be rephrased as “maximizing the number of watered flowers”. That is, the required answer is total number of flowers - maximum number of watered flowers.

Next, let’s consider how to search for the sprinkler position \(s\). Although \(s\) can be any non-negative real number, the actual number of watered flowers only changes when \(s\) passes through a plant’s coordinate \(X_i\). For example, even if we move \(s\) slightly, the number of watered flowers does not change as long as the set of plants included in the range \([s, s+D)\) remains the same. Therefore, it is sufficient to consider only the cases where \(s\) is set to \(0\) or is aligned with one of the plant coordinates \(X_i\).

Let’s consider finding the sum of \(P_j\) within the range satisfying \(X_i \leq X_j < X_i + D\) for all \(i\). Searching for this range from scratch for each \(i\) would take \(O(N^2)\) time, which is too slow for the constraint \(N \leq 2 \times 10^5\). However, since the coordinates \(X_i\) are monotonically increasing, as we move the sprinkler position \(s\) from left to right, both the left and right ends of the waterable range also move to the right. Therefore, the two-pointer technique (sliding window) is suitable for finding the sum in this range.

Algorithm

1. Calculate the total number of flowers total.
2. To account for the case where \(s = 0\), add a dummy plant with coordinate \(X_0 = 0\) and number of flowers \(P_0 = 0\) at the beginning.
3. Using the two-pointer technique, find the maximum right end right that satisfies the condition \(X[right] - X[left] < D\) for each left end left.
4. Maintain the sum of flowers current_sum within the interval [left, right], and update its maximum value max_watered.
5. Finally, output total - max_watered.

Complexity

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

Implementation Points

• By using 1-indexed arrays for coordinates \(X\) and flowers \(P\), and setting the values at index \(0\) to \(0\), we can naturally handle the \(s = 0\) case within the loop.

• In the two-pointer technique, the running sum is maintained in \(O(1)\) time by adding to current_sum as we advance the right pointer right, and subtracting from current_sum as we advance the left pointer left when the distance exceeds \(D\).

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    X = [0] * (N + 1)
    P = [0] * (N + 1)
    total = 0
    for i in range(1, N + 1):
        x, p = map(int, input().split())
        X[i] = x
        P[i] = p
        total += p
    
    max_watered = 0
    current_sum = 0
    left = 0
    
    for right in range(N + 1):
        current_sum += P[right]
        while X[right] - X[left] >= D:
            current_sum -= P[left]
            left += 1
        if current_sum > max_watered:
            max_watered = current_sum
            
    print(total - max_watered)

if __name__ == '__main__':
    solve()

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