Планировка

@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;
}

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
Генератор паролей (вариант №2) Maks 30.10.2026 Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .	Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .	Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .

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

	Планировка 01.09.2020, 19:19. Показов 3589. Ответов 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