Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
0 / 0 / 0
Регистрация: 27.04.2019
Сообщений: 38
1

Задача про провода: бинарный поиск

21.08.2019, 08:11. Показов 1536. Ответов 3
Метки нет (Все метки)

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= Li <= 10 000 000, все числа целые.

Входные данные
В первой строке находятся числа N и К. В следующих N строках - L1, L2, ..., LN, по одному числу в строке.

Выходные данные
Вывести одно число - полученную длину отрезков.

Примеры
входные данные
4 11
802
743
457
539
выходные данные
200
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.08.2019, 08:11
Ответы с готовыми решениями:

Задача про бинарный файл..
Добрый вечер) Вот возникла очередная проблемка с задачей по СИ++. Задача звучит таким образом:...

Задача на бинарный поиск
Решаю такую задачу: На столе в виде прямоугольника N×M лежат карточки, на которых написаны числа....

Задача на бинарный поиск в матрице
Задано матрицу А. Определить присутствие

Задача на линейный и бинарный поиск фамилии студента по первым буквам и целиком и по части телефонного номера
Организовать массив типа Студент со следующими полями: фамилия, имя, год рождения, номер телефона....

3
Эксперт C
26066 / 16256 / 3494
Регистрация: 24.12.2010
Сообщений: 35,626
21.08.2019, 09:57 2
Max aqq, Ввести данные сможете?
Пусть int S - суммарная длина исходных кусков (сможете посчитать?)
X = S/K
if (X==0) невозможно
Y = Сумма Li/X
Пока Y < K увеличиваете X на 1
Получившийся X и будет ответом

Добавлено через 1 минуту
Это алгоритм линейного поиска. Но, конечно, воспользоваться и бинарным. Что эффективнее.
0
0 / 0 / 0
Регистрация: 27.04.2019
Сообщений: 38
22.08.2019, 08:38  [ТС] 3
а можете описать алгоритм решения бинарным поиском, пожалуйста.
0
Эксперт C
26066 / 16256 / 3494
Регистрация: 24.12.2010
Сообщений: 35,626
22.08.2019, 10:05 4
Цитата Сообщение от Max aqq Посмотреть сообщение
можете описать алгоритм решения бинарным поиском,
Давайте сделаем так. Вы реализуете в коде (можно в псевдокоде) алгоритм линейного поиска, который я вам показал. А я вам покажу ту часть кода, которую надо изменить (и как), чтобы поиск стал бинарным
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.08.2019, 10:05

Доказать (про длину электрического провода)
Электрический провод натянут между двумя столбами, расстояние между ними l, высота столбов - a и b....

Подскажите про PCI-E провода разные и подсоединение к видеоадаптеру
Вот у меня БУДЕТ блок питания с PCI-E 6x(6+2) pin Есть уже видеокарта с питанием 8+4 pin. Они...

Разрыв провода питания и дата провода usb
Подскажите пожалуйста, мне требуется разрывать провод + питания, и D+ data провод у USB. т.е.: ...

Поиск заданного элемента в упорядоченном массиве(бинарный поиск)
Заполнить одномерный массив из n элементов по формуле приведенной в картинке. Размерность массива...

Поиск первого положительного элемента массива (бинарный поиск)
Нужен именно бинарный поиск,чтобы выводился первый положительный элемент из массива чисел(в массиве...

Поиск заданного элемента в упорядоченном массиве (бинарный поиск)
Заполнить одномерный массив из n элементов согласно таблицы. Размерность массива задать в виде...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.