Мережа ретрансляторів на Розломі Персея (Розбір)

У задачі потрібно знайти найбільше значення $d$ таке, що можна обрати $k$ із $n$ аванпостів, у яких відстань між будь-якими двома обраними не менша за $d$. Перебирати самі набори безнадійно — їх \binom{n}{k} — але перебирати відповідь легко, бо перевірка фіксованого $d$ зводиться до жадібного алгоритму за лінійний час.

Це працює завдяки монотонності. Якщо $k$ ретрансляторів можна розмістити так, що всі попарні відстані не менші за $d$, то те саме розміщення задовольняє вимогу і для будь-якого d' < d. Отже, допустимі значення утворюють префікс 1, 2, \dots, D, і відповідь — це саме останнє допустиме значення $D$. Це рівно та властивість, якої потребує бінарний пошук.

Перевірка допустимості

Зафіксуємо кандидата $d$ і запитаємо: чи можна обрати щонайменше $k$ аванпостів так, щоб сусідні обрані координати відрізнялися хоча б на $d$? Оскільки аванпости лежать на прямій і задані у зростаючому порядку, важливі лише сусідні обрані аванпости — якщо сусіди в наборі віддалені на $\ge d$, то й усі інші пари теж.

Жадібний алгоритм: беремо x_1, далі йдемо зліва направо і беремо аванпост щоразу, коли він віддалений щонайменше на $d$ від останнього взятого. Нехай $c(d)$ — кількість обраних таким чином аванпостів; тоді $d$ допустиме тоді й лише тоді, коли c(d) \ge k.

Оптимальність жадібності доводиться обміном. Нехай деякий коректний набір розміру $m$ використовує позиції p_1 < p_2 < \dots < p_m, а g_1 < g_2 < \dots — вибір жадібного алгоритму. За індукцією g_i \le p_i для всіх $i$: для i = 1 це так, бо g_1 = x_1 — найлівіший аванпост; якщо ж g_i \le p_i, то p_{i+1} \ge p_i + d \ge g_i + d, тобто аванпост на відстані $\ge d$ від g_i існує не пізніше за p_{i+1} — а жадібний бере перший такий, звідки g_{i+1} \le p_{i+1}. Отже, жадібний алгоритм ніколи не відстає і обирає не менше аванпостів, ніж будь-який коректний набір.

Бінарний пошук

Відповідь лежить у межах [1, (x_n - x_1)/(k-1)]: координати — різні цілі числа, тому відстань $1$ завжди досяжна, а $k$ обраних аванпостів вкладаються у проміжок довжини не більше x_n - x_1 із k-1 проміжками довжини щонайменше $d$ кожен, звідки

Виконуємо бінарний пошук на цьому відрізку, запускаючи жадібну перевірку на кожному кроці, і зберігаємо найбільше $d$, для якого c(d) \ge k.

Реалізація

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

int n, k;
vector<int> x;

// скільки аванпостів обирає жадібний алгоритм при мінімальній відстані d
int count_relays(int d) {
    int cnt = 1, last = x[0];
    for (int i = 1; i < n; i++) {
        if (x[i] - last >= d) {
            cnt++;
            last = x[i];
        }
    }
    return cnt;
}

int main() {
    scanf("%d %d", &n, &k);
    x.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &x[i]);

    int lo = 1, hi = (x[n-1] - x[0]) / (k - 1), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (count_relays(mid) >= k) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    printf("%d\n", ans);
    return 0;
}

Варто перевірити два граничні випадки. Якщо k = n, використовуються всі аванпости і відповідь дорівнює найменшому проміжку між сусідами \min_i (x_{i+1} - x_i) — жадібний бере всі аванпости саме для цього $d$ і пропускає один для будь-якого більшого. Якщо k = 2, відповідь дорівнює x_n - x_1, що збігається з верхньою межею пошуку. Ділення на k-1 коректне, оскільки k \ge 2.

Переповнення неможливе: координати не перевищують 10^9, а всі обчислювані величини — різниці двох координат, тож достатньо 32-бітної знакової арифметики.

Аналіз складності:

• Часова складність: O(n \log X), де X = x_n - x_1 \le 10^9 — близько $30$ жадібних проходів масивом

• Просторова складність: $O(n)$ для зберігання координат