Overview

When cities are arranged on a straight line, this problem asks us to build a communication network at minimum cost such that removing any single city still leaves the remaining cities connected.

The answer is very simple. If we let the westernmost city position be \(\min X_i\) and the easternmost city position be \(\max X_i\), then the minimum cost is:

\(2(\max X_i - \min X_i)\)

Analysis

Let the cities sorted from west to east be:

\(Y_1 < Y_2 < \cdots < Y_N\)

Now, let’s focus on the intervals between adjacent cities, namely:

the interval between \(Y_i\) and \(Y_{i+1}\).

Suppose there is at most \(1\) communication line crossing this interval.

Then, by removing the city that is an endpoint of that line, there would be no lines connecting the west side and east side of this interval.
As a result, the remaining cities can no longer communicate with each other, and the condition is not satisfied.

Therefore, for every adjacent interval, at least \(2\) communication lines must cross it.

Now, suppose a communication line connects \(Y_l\) and \(Y_r\).
Its cost is:

\(Y_r - Y_l\)

This can be thought of as the sum of the lengths of all adjacent intervals in between.

In other words, the total cost of communication lines can be expressed as the sum of:

“length of each adjacent interval” \(\times\) “number of lines crossing that interval”

Since at least \(2\) lines must cross each adjacent interval, the total cost is at least:

\(2 \times \{(Y_2 - Y_1) + (Y_3 - Y_2) + \cdots + (Y_N - Y_{N-1})\}\)

By telescoping, this becomes:

\(2(Y_N - Y_1)\)

This means that no matter what network we build, the cost must be at least:

\(2(\max X_i - \min X_i)\)

On the other hand, this value can actually be achieved.

Arrange the cities from west to east and form the cycle:

\(Y_1 - Y_2 - Y_3 - \cdots - Y_N - Y_1\)

The cost in this case is:

• The total cost of connecting adjacent cities is \(Y_N - Y_1\)
• The cost of connecting \(Y_N\) back to \(Y_1\) is \(Y_N - Y_1\)

So the total is:

\(2(Y_N - Y_1)\)

A cycle remains connected (as a path) even after removing any single vertex.
Therefore, the condition is satisfied.

Thus, the minimum cost is:

\(2(\max X_i - \min X_i)\)

If we naively consider communication lines between all pairs of cities, there are \(O(N^2)\) candidate lines.
However, since \(N \leq 10^6\), an approach that examines all combinations is infeasible.

The key insight in this problem is realizing that the final answer depends only on the westernmost and easternmost cities.

Algorithm

For the given city positions \(X_i\), find the minimum and maximum values.

1. Find \(\min X_i\)
2. Find \(\max X_i\)
3. Output \(2(\max X_i - \min X_i)\)

There is no need to actually sort the cities.
Knowing only the minimum and maximum values is sufficient.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

The answer is:

\(2(\max X_i - \min X_i)\)

While reading the input, simply update the minimum mn and maximum mx.

long long mn = LLONG_MAX, mx = LLONG_MIN;

for (int i = 0; i < N; i++) {
    long long x;
    cin >> x;
    mn = min(mn, x);
    mx = max(mx, x);
}

cout << 2 * (mx - mn) << '\n';

The position values can be up to \(10^9\), but using long long for safety is recommended.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long mn = LLONG_MAX, mx = LLONG_MIN;
    for (int i = 0; i < N; i++) {
        long long x;
        cin >> x;
        mn = min(mn, x);
        mx = max(mx, x);
    }

    cout << 2 * (mx - mn) << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.