Задача "Субботник"

@Zo_Omer · Регистрация: 06.11.2012

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

В классе учатся N человек. Руководитель получил указание направить на субботник R бригад по С человек в каждой.
Все бригады будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.
Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально.

Формат входных данных (имя входного файла: input.txt)
Сначала вводятся натуральные числа N, R и C — количество человек в классе, количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ N ≤ 100 000). Далее вводятся N целых чисел — рост каждого из N учеников. Рост — натуральное число, не превышающее 1 000 000 000.

Формат выходных данных (имя выходного файла: output.txt)
Выведите одно число – наименьшее возможное значение максимального числа неудобства сформированных бригад.

@TokyoGhoul · 05.11.2018, 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
#include <bits/stdc++.h>
 
using namespace std;
 
int n,t,c;
   
int check(int k,int a[])
{
    int kol=0,i=1;
    while(i<=n-c+1)
    if(a[i+c-1]-a[i]<=k)
    {
        kol++;
        i=i+c;
    }
        else i++;
    if(kol>=t) return 1;
    else return -1;
   
}
 
int main()
{
    int i,m,r,l,min;
    scanf("%d%d%d",&n,&t,&c);
    int a[n+1];
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    if(n==c)
    {
        printf("%d",a[n]-a[1]);
        return 0;
    }
    l=0;
    r=a[n]-a[1];
    min=r;
    while(l<r)
    {
        m=(l+r)/2;
        if(check(m,a)>0)
        {
            r=m;   
            if(m<min) min=m;
        }
       
        else l=m+1;
    }
    printf("%d",min);
    return 0;
}

@кот Бегемот · 05.11.2018, 22:15

TokyoGhoul, я восхищён Вами! Зайти в раздел паскаль и написать там решение на С++... Это шедевр тупости.
Даже если Ваше решение верно, оно здесь никому на хер не нужно.

PS
Для слишком строгих ревнителей цензуры и нравственности
Хер - название буквы Х в древнерусском и старославянском языках, а так же испанское название муниципалитета Жер в Каталонии.
Если кому-то показалось что-то другое, то Вам показалось.

@TokyoGhoul · 09.11.2018, 16:45

ахах, извиняюсь, я просто искал решение одной задачи тут, нашёл только этот вопрос, а когда решил задачу, то захотел помочь автору вопроса), и специально для этого зарегистрировался и закинул решение. Не знал, что у вас тут так всё серьёзно и делится по языкам, ну ладно, буду знать, ну и вдруг моё решение кому-нибудь пригодится)

@Zo_Omer · 09.11.2018, 17:58 **[ТС]**

Лол, я задавал этот вопрос 6 лет назад... я даже забыл что регистрировался на этом форме... я уже вуз успел закончить. Вы хоть на даты смотрите!

@TokyoGhoul · 09.11.2018, 18:33

ахах, я в прошлом ответе выразился, что хотел помочь тебе - неправильно выразился, я хотел оставить этот ответ, чтобы, если кто-то будет искать ответ на поставленную задачу, то открыл эту тему и нашёл его)

@Alex1603 · 07.08.2019, 21:04

Спасибо за ответ.

@chewy_pegasus · 31.01.2022, 20:10

Ну вообще да, мне пригодилось только что

@Пытливый · 31.01.2022, 22:55

Как говорил Хазанов - "ну это же не очень скорая помощь", так что 6 лет задержки и ответ на другом языке - нормально.

@chewy_pegasus · 31.01.2022, 22:59

Что интересно, то это то, что я искал именно на c++. Как я сюда попал - до сих пор не понял... Возможно сказываются мои паскалевские корни

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@Zo_Omer 0 / 0 / 2 Регистрация: 06.11.2012 Сообщений: 10

	Задача "Субботник" 06.11.2012, 20:32. Показов 13151. Ответов 9 Метки нет (Все метки) В классе учатся N человек. Руководитель получил указание направить на субботник R бригад по С человек в каждой. Все бригады будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады. Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Формат входных данных (имя входного файла: input.txt) Сначала вводятся натуральные числа N, R и C — количество человек в классе, количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ N ≤ 100 000). Далее вводятся N целых чисел — рост каждого из N учеников. Рост — натуральное число, не превышающее 1 000 000 000. Формат выходных данных (имя выходного файла: output.txt) Выведите одно число – наименьшее возможное значение максимального числа неудобства сформированных бригад. 0

@кот Бегемот Платежеспособный зверь 8966 / 4389 / 1655 Регистрация: 28.10.2009 Сообщений: 11,647
	05.11.2018, 22:15
	TokyoGhoul, я восхищён Вами! Зайти в раздел паскаль и написать там решение на С++... Это шедевр тупости. Даже если Ваше решение верно, оно здесь никому на хер не нужно. PS Для слишком строгих ревнителей цензуры и нравственности Хер - название буквы Х в древнерусском и старославянском языках, а так же испанское название муниципалитета Жер в Каталонии. Если кому-то показалось что-то другое, то Вам показалось. 0

@TokyoGhoul 3 / 3 / 0 Регистрация: 05.11.2018 Сообщений: 3
	09.11.2018, 16:45
	ахах, извиняюсь, я просто искал решение одной задачи тут, нашёл только этот вопрос, а когда решил задачу, то захотел помочь автору вопроса), и специально для этого зарегистрировался и закинул решение. Не знал, что у вас тут так всё серьёзно и делится по языкам, ну ладно, буду знать, ну и вдруг моё решение кому-нибудь пригодится) 1

@Zo_Omer 0 / 0 / 2 Регистрация: 06.11.2012 Сообщений: 10
	09.11.2018, 17:58 [ТС]
	Лол, я задавал этот вопрос 6 лет назад... я даже забыл что регистрировался на этом форме... я уже вуз успел закончить. Вы хоть на даты смотрите! 0

@TokyoGhoul 3 / 3 / 0 Регистрация: 05.11.2018 Сообщений: 3
	09.11.2018, 18:33
	ахах, я в прошлом ответе выразился, что хотел помочь тебе - неправильно выразился, я хотел оставить этот ответ, чтобы, если кто-то будет искать ответ на поставленную задачу, то открыл эту тему и нашёл его) 1

@Alex1603 0 / 0 / 0 Регистрация: 10.03.2019 Сообщений: 16
	07.08.2019, 21:04
	Спасибо за ответ. 0

@chewy_pegasus 0 / 0 / 0 Регистрация: 10.10.2021 Сообщений: 3
	31.01.2022, 20:10
	Ну вообще да, мне пригодилось только что 0

@Пытливый 3763 / 2267 / 705 Регистрация: 29.05.2013 Сообщений: 9,622
	31.01.2022, 22:55
	Как говорил Хазанов - "ну это же не очень скорая помощь", так что 6 лет задержки и ответ на другом языке - нормально. 0

@chewy_pegasus 0 / 0 / 0 Регистрация: 10.10.2021 Сообщений: 3
	31.01.2022, 22:59
	Что интересно, то это то, что я искал именно на c++. Как я сюда попал - до сих пор не понял... Возможно сказываются мои паскалевские корни 0