Overview

In this problem, we are given \(N\) flowerbeds arranged on a straight line. We want to place one sprinkler that can water a range of length \(D\) in order to minimize the number of flowers that cannot be watered.

Analysis

• First, minimizing the number of flowers that cannot be watered is equivalent to maximizing the number of flowers that can be watered.
• When the sprinkler is placed at coordinate \(s\), the range it covers is \(s \leq X_i < s + D\). The flowerbeds satisfying this condition form a contiguous interval when sorted by coordinate.
• When considering the optimal placement \(s\) of the sprinkler, aligning \(s\) exactly with the coordinate \(X_l\) of some flowerbed \(l\) allows us to maximize the covered range without any waste. Therefore, it is sufficient to consider only the \(N\) possible placements where “the left end is aligned with the \(l\)-th flowerbed.”
• For each \(l\), the rightmost flowerbed \(r-1\) that can be watered must satisfy \(X_{r-1} - X_l < D\). In other words, we advance \(r\) until just before \(X_r - X_l \geq D\) holds.
• If we search for \(r\) starting from \(0\) for every \(l\), the time complexity will be \(O(N^2)\), which will result in a Time Limit Exceeded (TLE) under the constraint \(N \leq 2 \times 10^5\).
• However, as \(l\) moves to the right, the \(r\) that satisfies the condition \(X_r - X_l < D\) also always moves to the right (or stays in place). By utilizing this monotonicity, we can use the “two-pointer technique” to find the answer while moving \(l\) and \(r\) together.

Algorithm

We can find the maximum number of watered flowers using the two-pointer technique. 1. Precompute the sum of all flowers across all flowerbeds, stored in total. 2. Loop the left pointer l from \(0\) to \(N-1\). 3. While the right pointer r is less than \(N\) and satisfies \(X_r - X_l < D\), add \(P_r\) to the current sum of flowers in the interval current_sum, and increment r by \(1\). 4. If current_sum exceeds the maximum value found so far ans_watered, update ans_watered. 5. Before incrementing l by \(1\), subtract \(P_l\) from current_sum (removing the \(l\)-th flowerbed from the interval). 6. Finally, total - ans_watered will be the minimum number of flowers that cannot be watered.

Complexity

• Time Complexity: \(O(N)\) (Since the left pointer l and the right pointer r each move at most \(N\) times in the two-pointer approach)
• Space Complexity: \(O(N)\) (To store the coordinates \(X\) and the number of flowers \(P\) in arrays)

Implementation Points

• The coordinates of the flowerbeds \(X_i\) and the number of flowers \(P_i\) can be up to \(10^9\), and \(N\) can be up to \(2 \times 10^5\). Therefore, computing the sum can cause an overflow with 32-bit integers (int type). It is necessary to use 64-bit integers (long long type) for variables that store the sum and maximum values.

  Source Code

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;
    
    vector<long long> X(N), P(N);
    long long total = 0;
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> P[i];
        total += P[i];
    }
    
    long long ans_watered = 0;
    long long current_sum = 0;
    int r = 0;
    
    for (int l = 0; l < N; ++l) {
        while (r < N && X[r] - X[l] < D) {
            current_sum += P[r];
            r++;
        }
        ans_watered = max(ans_watered, current_sum);
        current_sum -= P[l];
    }
    
    cout << total - ans_watered << "\n";
    
    return 0;
}

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