Паскаль! ! провода дано 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, по одному числу в строке. выходные данные вывести одно число - полученную длину отрезков.
// Внимание! Если программа не работает, обновите версию!
begin
var ЕстьКусков,НадоКусков:integer;
Readln(ЕстьКусков,НадоКусков);
var Длины:=ReadArrInteger(ЕстьКусков);
var ОбщаяДлина:=Длины.Sum;
if НадоКусков>ОбщаяДлина then Writeln(0)
else begin
var ДлинаКуска:=ОбщаяДлина div НадоКусков;
repeat
if Длины.Select(Кусок->Кусок div ДлинаКуска).Sum >=НадоКусков then break
else ДлинаКуска-=1;
until false;
writeln(ДлинаКуска)
end
end.
Пример
4 11
802 743 457 539
200
Ввод -вывод
5 12
6
7
8
9
10
длина отрезка: 3
1. Входные данные:
Первая строка содержит значения n и k, где n - количество отрезков провода, а k - количество отрезков, которые нужно получить.
В следующих n строках содержатся длины отдельных отрезков провода l1, l2, ..., ln.
2. Выходные данные:
Необходимо вывести одно число - длину полученных отрезков провода.
3. Алгоритм решения:
Данное задание требует разрезания отрезков провода на равные по длине части. Чтобы найти максимальную длину отрезков, которую можно получить, нужно применить подходящий алгоритм.
Вариант 1: Поиск делителя длин всех отрезков провода.
- Найдите наименьшую длину отрезка провода (min_length) среди всех введенных отрезков.
- Инициализируйте переменную max_possible_length в min_length и установите в нее значение min_length.
- Начните цикл с max_possible_length и уменьшайте его на 1 на каждой итерации до тех пор, пока не достигнете значения 1.
- Внутри цикла проверьте, можно ли разделить каждый отрезок провода на части равной длины, которую мы проверяем.
- Если все отрезки можно разделить на целое количество частей, то обновите значение max_possible_length, присвоив ему текущую проверяемую длину.
- Если вдруг все отрезки не разрезаются на равные части, то перейдите к следующей проверяемой длине.
- Выведите значение max_possible_length.
Вариант 2: Использование бинарного поиска.
- Находим сумму всех длин отрезков провода.
- Устанавливаем значения left и right для бинарного поиска:
- left = 1 (минимальная возможная длина отрезка)
- right = сумма всех длин отрезков.
- Запускаем цикл бинарного поиска:
- while left <= right:
- Вычисляем среднее значение middle:
- middle = (left + right) / 2
- Используя среднее значение, мы можем проверить, можно ли получить k отрезков длиной middle:
- Найдем количество отрезков, которое можно получить, разделив каждый отрезок провода на длину middle.
- Если полученное количество отрезков больше k, то это значит, что мы можем получить более короткие отрезки.
- Изменим left на middle + 1.
- Если количество отрезков, которое можно получить, меньше или равно k, то это значит, что мы можем получить более длинные отрезки.
- Изменим right на middle - 1.
- После выхода из цикла у нас будет максимальная длина отрезков, которую можно получить.
- Выводим значение максимальной длины.
4. Пример решения на Python:
```python
def check_segments_lengths(n, k, segments_lengths, length):
total_segments = 0
for length_segment in segments_lengths:
total_segments += length_segment // length
if total_segments >= k:
return True
return False
def find_max_length(n, k, segments_lengths):
left = 1
right = sum(segments_lengths)
result = 0
while left <= right:
middle = (left + right) // 2
if check_segments_lengths(n, k, segments_lengths, middle):
result = middle
left = middle + 1
else:
right = middle - 1
return result
n, k = map(int, input().split())
segments_lengths = [int(input()) for _ in range(n)]
max_length = find_max_length(n, k, segments_lengths)
print(max_length)
```
5. Обоснование решения:
- Применяем бинарный поиск, который позволяет нам быстро находить максимально возможную длину отрезка провода.
- Анализируем каждую среднюю длину в бинарном поиске и проверяем, можно ли из отрезков получить требуемое количество отрезков.
- Используем функцию check_segments_lengths, которая проверяет, можно ли из отрезков получить k отрезков длиной length.
- Если получаемое количество отрезков больше или равно k, то увеличиваем left, иначе уменьшаем right.
- Когда left > right, мы нашли максимально возможную длину отрезка.
Надеюсь, данное объяснение поможет школьнику лучше понять решение задачи.