Планировка

@Jorka · Регистрация: 25.07.2020

Студворк — интернет-сервис помощи студентам

Вы — мэр города Лайнбурга. Как можно догадаться из названия, все дома в вашем городе расположены вдоль одной бесконечной в обе стороны прямой. Прямо сейчас перед вами стоит задача спроектировать новый район. Задача осложняется двумя факторами:

Для строительства вам доступны только n позиций вдоль прямой, заданные своими координатами x1,…,xn.

В своей предвыборной программе вы обещали построить m школ, которые также можно строить только в точках с координатами xi. В точках, в которых не будут построены школы, будут построены дома (бюджет надо осваивать целиком!).

Поскольку вы грамотный политик, то хотите, чтобы вашим гражданам было комфортно добираться от дома до школы. Ясное дело, что жители Лайнбурга рациональны и будут ездить от дома до ближайшей школы, а если таких несколько, то до любой из них. Расстоянием между домом и школой в этой задаче считается абсолютная разница координат.

Таким образом, ваша задача состоит в том, чтобы спроектировать новый район Лайнбурга так, чтобы минимизировать максимальное расстояние между домом и ближайшей школой.

В этой задаче мы не просим вас предъявлять подходящее расположение школ, достаточно вывести искомый минимальный максимум расстояния между домом и ближайшей школой.

Формат входных данных
В первой строчке вводятся два целых числа: n

m. Во второй строчке вводятся координаты, в которых можно строить: x1 x2 ... xn
1≤m≤n≤10**5 Все xi целые. Все xi различные. 0≤xi≤10**9

Формат результата
Одно целое число — ответ на задачу.

Примеры
Входные данные
10 4
1 7 9 2 10 15 17 24 20 21
Результат работы
3

@ram876 · 11.09.2020, 18:02

Сообщение от Алексей1153

не знаю за Лайнбург, но у нас это вполне обычное явление

У нас нормально даже когда улица Бухарская, а дома там А.Кутуя, Родины и Бухарская.

@LegionK · 11.09.2020, 20:56

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
#define ll long long
 
bool ok(ll n,ll m,vector<ll>&v,ll k)
{
    
    ll pos = -k-1;
    
    ll j = 0;
    
    for(ll i = 0;i<n;++i){
        
        if(!m){
            
            if(pos+k >= v.back())return 1;
            else return 0;
            
        }   
        
        if(pos+k >= v[i])continue;
        
        --m;
        
        ll need = v[i]+k;
        
        while(1){
            
            if(j == n)break;
            
            if(v[j] > need)break;
            
            ++j;
            
        }
        
        --j;
        
        pos = v[j];
        
    }
    
    if(pos+k >= v.back())return 1;
    else return 0;
    
}
 
ll bs(ll n,ll m,vector<ll>&v){
    
    ll l(-1),r(1e10);
    
    while(l+1 < r)
    {
        
        ll mid = (l+r)/2;
        
        if(ok(n,m,v,mid))r = mid;
        else l = mid;
        
    }
    
    return r;
}
 
 
int main() 
{
    
    ll n,m;
    cin >> n >> m;
    
    vector<ll>v(n);
    for(ll i = 0;i<n;++i)cin >> v[i];
    
    sort(v.begin(),v.end());
    
    cout << bs(n,m,v);
    
    
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302

	Планировка 01.09.2020, 19:19. Показов 3517. Ответов 21 Метки нет (Все метки) Вы — мэр города Лайнбурга. Как можно догадаться из названия, все дома в вашем городе расположены вдоль одной бесконечной в обе стороны прямой. Прямо сейчас перед вами стоит задача спроектировать новый район. Задача осложняется двумя факторами: Для строительства вам доступны только n позиций вдоль прямой, заданные своими координатами x1,…,xn. В своей предвыборной программе вы обещали построить m школ, которые также можно строить только в точках с координатами xi. В точках, в которых не будут построены школы, будут построены дома (бюджет надо осваивать целиком!). Поскольку вы грамотный политик, то хотите, чтобы вашим гражданам было комфортно добираться от дома до школы. Ясное дело, что жители Лайнбурга рациональны и будут ездить от дома до ближайшей школы, а если таких несколько, то до любой из них. Расстоянием между домом и школой в этой задаче считается абсолютная разница координат. Таким образом, ваша задача состоит в том, чтобы спроектировать новый район Лайнбурга так, чтобы минимизировать максимальное расстояние между домом и ближайшей школой. В этой задаче мы не просим вас предъявлять подходящее расположение школ, достаточно вывести искомый минимальный максимум расстояния между домом и ближайшей школой. Формат входных данных В первой строчке вводятся два целых числа: n m. Во второй строчке вводятся координаты, в которых можно строить: x1 x2 ... xn 1≤m≤n≤105 Все xi целые. Все xi различные. 0≤xi≤109 Формат результата Одно целое число — ответ на задачу. Примеры Входные данные 10 4 1 7 9 2 10 15 17 24 20 21 Результат работы 3 1