Overview

This problem asks us to place \(K\) shelters for \(N\) settlements on a number line, minimizing the maximum distance \(d\) from each settlement to its nearest shelter.

By focusing on the typical structure of “minimizing the maximum value,” we can efficiently find the optimal solution by binary searching on the answer (specifically \(2d\), which is twice the distance).

---

Analysis

1. The Range a Shelter Can Cover

Let \(P\) be the coordinate of a shelter and \(d\) be the maximum allowable distance. The coordinates \(X_i\) of settlements that this shelter can cover must satisfy: $\(P - d \leq X_i \leq P + d\)$

The maximum length (width) from the left end to the right end of this interval is \((P + d) - (P - d) = 2d\). In other words, “the maximum distance is at most \(d\)” is equivalent to “for the set of settlements covered by each shelter, the distance between the rightmost and leftmost settlements is at most \(2d\)”.

Setting \(D = 2d\), the problem can be rephrased as: “When dividing settlements into groups, can we ensure that (maximum coordinate \(-\) minimum coordinate) within each group is at most \(D\)?”

2. The Condition “Every Shelter Must Accept at Least One Settlement”

Exactly \(K\) shelters must be placed. Suppose the minimum number of groups when dividing into groups with maximum width \(D\) is \(cnt\). - If \(cnt > K\): It is impossible to divide into \(K\) or fewer groups while maintaining width \(D\). Therefore, the maximum distance \(d = D/2\) is unachievable. - If \(cnt \leq K\): It is possible to divide into exactly \(K\) groups while maintaining width \(D\). This is because we can further split groups with \(2\) or more elements into smaller groups, increasing the number of groups to exactly \(K\) while keeping the maximum width within each group at most \(D\) (this is always possible since \(K \leq N\)).

Therefore, for a given \(D\), we only need to solve the decision problem: “When covering settlements with intervals of width at most \(D\), is the minimum number of intervals required at most \(K\)?”

3. Solving the Decision Problem (Greedy Method)

“The minimum number of intervals of width at most \(D\) needed to cover all settlements” can be found greedily from left to right: 1. Let \(L\) be the coordinate of the leftmost settlement not yet covered. 2. Consider the interval \([L, L+D]\) of width \(D\) starting at \(L\). 3. Cover all settlements within this interval with the same shelter. 4. If there are still uncovered settlements, return to step 1 and create a new interval.

If the number of intervals \(cnt\) obtained by this method is at most \(K\), then that \(D\) is achievable.

4. Monotonicity and Binary Search

The following monotonicity holds: “The larger the width \(D\), the smaller (or unchanged) the required number of intervals \(cnt\).” Therefore, we can perform binary search on the minimum \(D\).

---

Algorithm

1. Set the binary search range

   • Minimum value: low = 0
   • Maximum value: high = X[N-1] - X[0] (the maximum width when covering all settlements with a single shelter)

2. Perform binary search

   • Set mid = (low + high) / 2 and call check(mid).
   • If check(mid) returns true (coverable with \(K\) or fewer groups), try a smaller \(D\) by setting high = mid - 1.
   • If check(mid) returns false, a larger \(D\) is needed, so set low = mid + 1.

3. Implementation of the decision function check(D)

   • Starting from the leftmost settlement, include settlements in the same group as long as their distance from the current interval’s left end \(L\) does not exceed \(D\).
   • When it exceeds \(D\), create a new group and set that settlement as the new left end \(L\).
   • Return true if the final group count \(cnt\) is at most \(K\), otherwise return false.

---

Complexity

• Time Complexity: \(O(N \log (\max X_i))\) The number of binary search steps is \(O(\log(\max X_i))\). Since the maximum coordinate value is \(10^9\) by the constraints, the number of iterations is about \(30\). The decision function check at each step only scans the settlements from left to right once, taking \(O(N)\). The overall complexity is \(O(N \log (\max X_i))\), which is sufficiently fast (even with \(N = 2 \times 10^5\), it requires only about \(6 \times 10^6\) operations, easily fitting within the time limit).

• Space Complexity: \(O(N)\) Only the array memory for storing the settlement coordinates \(X_1, \dots, X_N\) is needed.

---

Implementation Notes

• Integer Processing: The problem statement mentions that “the distance \(d\) is either an integer or a half-integer, and \(2d\) is always a non-negative integer.” By searching for the value \(D = 2d\) (twice the distance) from the start, we can handle everything using only integer types (long long) without any errors, completely avoiding the use of floating-point numbers (such as double).

• Fast I/O: In C++, since the input can be as large as \(N = 2 \times 10^5\), we use std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); to speed up input/output.

  Source Code

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

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> X(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i];
    }

    // 距離の2倍である D に対する判定関数
    auto check = [&](long long D) {
        int cnt = 0;
        int i = 0;
        while (i < N) {
            cnt++;
            long long L = X[i];
            // スパンが D 以下である限り、同じ区間に含める
            while (i < N && X[i] - L <= D) {
                i++;
            }
        }
        return cnt <= K;
    };

    // 二分探索
    long long low = 0, high = X[N - 1] - X[0];
    long long ans = high;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.