Overview

This problem asks us to find the minimum communication range \(K\) such that all \(N\) base stations placed on a line can communicate with each other, either directly or indirectly.

Analysis

From a graph theory perspective, this problem can be rephrased as finding “the minimum edge length such that all vertices become connected.”

Key Insight

Since the base stations are on a straight line, it is sufficient to ensure that adjacent base stations can communicate with each other in order for all base stations to be able to communicate.

For example, if the coordinates are sorted as \(X_1, X_2, \dots, X_N\): - \(X_1\) and \(X_2\) can communicate (distance \(\leq K\)) - \(X_2\) and \(X_3\) can communicate (distance \(\leq K\)) - … - \(X_{N-1}\) and \(X_N\) can communicate (distance \(\leq K\))

If all these conditions are satisfied, then any base station can reach any other base station by relaying through neighboring base stations.

Determining the Minimum \(K\)

Let the gap between all adjacent base stations be \(D_i = X_{i+1} - X_i\). The communication range \(K\) must be at least as large as every \(D_i\) (\(K \geq D_i\)). The minimum \(K\) that satisfies this condition for all \(i\) is the maximum value among the distances between adjacent base stations.

Algorithm

1. Sort the base station coordinates \(X_i\) in ascending order.
2. For the sorted coordinates, compute all distances \(X_{i+1} - X_i\) between adjacent base stations.
3. Find and output the maximum among those distances.
4. However, when \(N=1\), no communication is needed, so the answer is \(0\).

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the coordinates takes \(O(N \log N)\). The subsequent distance computation and maximum search take \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the base station coordinates.

Implementation Notes

• Since the base station coordinates are not necessarily given in ascending order, sorting must always be performed first.

• Since the maximum value of \(N\) is as large as \(2 \times 10^5\), in Python it is efficient to read input quickly using methods such as sys.stdin.read().split().

• Handle the \(N=1\) case properly to avoid errors (with the logic used here, the loop does not execute, so setting the initial value to \(0\) naturally handles this case).

  Source Code

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 基地局の数 N を取得
    n = int(input_data[0])
    
    # 基地局が1つの場合は通信範囲は 0 で良い
    if n <= 1:
        print(0)
        return
    
    # 基地局の座標 X を取得し、昇順にソートする
    x = list(map(int, input_data[1:]))
    x.sort()
    
    # 隣り合う基地局間の距離の最大値が、求める最小の K となる
    max_diff = 0
    for i in range(n - 1):
        diff = x[i+1] - x[i]
        if diff > max_diff:
            max_diff = diff
            
    # 結果を出力
    print(max_diff)

if __name__ == "__main__":
    solve()

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