Задачи на оптимизацию с бинарным поиском.
Задачи на поиск минимального или максимального значения с использованием бинарного поиска.
Условие:
Коко любит бананы. Есть n кучек бананов, i-я кучка имеет piles[i] бананов. Охранники ушли и вернутся через h часов.
Коко может решить, с какой скоростью k (бананов в час) она будет есть. Каждый час она выбирает какую-то кучку и съедает k бананов из неё.
Верните минимальное целое k, такое что Коко сможет съесть все бананы за h часов.
Примеры:
Ввод: piles = [3, 6, 7, 11], h = 8
Вывод: 4
Ввод: piles = [30, 11, 23, 4, 20], h = 5
Вывод: 30
Решение:
import math
def minEatingSpeed(piles, h):
def can_eat_all(speed):
hours = sum(math.ceil(pile / speed) for pile in piles)
return hours <= h
left, right = 1, max(piles)
result = right
while left <= right:
mid = left + (right - left) // 2
if can_eat_all(mid):
result = mid
right = mid - 1
else:
left = mid + 1
return resultОбъяснение:
can_eat_all(speed) проверяет, можно ли съесть все за h часовСложность: O(n × log m)
Условие:
Верните минимальную грузоподъёмность корабля, чтобы все грузы были доставлены за days дней.
Примеры:
Ввод: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Вывод: 15
Решение:
def shipWithinDays(weights, d):
def can_ship(capacity):
days = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
days += 1
current_load = w
else:
current_load += w
return days <= d
left = max(weights)
right = sum(weights)
result = right
while left <= right:
mid = left + (right - left) // 2
if can_ship(mid):
result = mid
right = mid - 1
else:
left = mid + 1
return resultСложность: O(n × log(sum(weights)))
Условие:
Разделите массив на k непустых непрерывных подмассивов так, чтобы максимальная сумма среди этих подмассивов была минимальной.
Примеры:
Ввод: nums = [7, 2, 5, 10, 8], k = 2
Вывод: 18
Решение:
def splitArray(nums, k):
def can_split(max_sum):
count = 1
current_sum = 0
for num in nums:
if current_sum + num > max_sum:
count += 1
current_sum = num
if count > k:
return False
return True
left = max(nums)
right = sum(nums)
result = right
while left <= right:
mid = left + (right - left) // 2
if can_split(mid):
result = mid
right = mid - 1
else:
left = mid + 1
return resultСложность: O(n × log(sum(nums)))
Условие:
Даны два отсортированных массива nums1 и nums2. Найдите медиану объединённого отсортированного массива.
Примеры:
Ввод: nums1 = [1, 3], nums2 = [2]
Вывод: 2.0
Ввод: nums1 = [1, 2], nums2 = [3, 4]
Вывод: 2.5
Решение:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
partition1 = (left + right) // 2
partition2 = (m + n + 1) // 2 - partition1
maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
minRight1 = float('inf') if partition1 == m else nums1[partition1]
maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
minRight2 = float('inf') if partition2 == n else nums2[partition2]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
if (m + n) % 2 == 0:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
else:
return max(maxLeft1, maxLeft2)
elif maxLeft1 > minRight2:
right = partition1 - 1
else:
left = partition1 + 1
raise ValueError("Input arrays are not sorted")Объяснение:
Сложность: O(log(min(m, n)))
| Задача | Диапазон | Проверка |
|---|---|---|
| Koko Eating | [1, max(piles)] | hours <= h |
| Ship Packages | [max, sum] | days <= d |
| Split Array | [max, sum] | count <= k |
| Median | [0, m] | maxLeft1 <= minRight2 |
# ❌ Неправильно
left = 0 # Для грузоподъёмности не может быть 0!
# ✅ Правильно
left = max(weights) # Минимум: самый тяжёлый груз# ❌ Неправильно
if can_achieve(mid):
right = mid - 1 # Не сохраняем!
# ✅ Правильно
if can_achieve(mid):
result = mid # Сохраняем возможный ответ
right = mid - 1Binary Search: Минимум/Максимум — поиск оптимального значения.
Ключевые принципы:
Далее: DFS: Основы