i-го — costs[i]. Лео и Мия покупают подарки вместе и договариваются о правилах оплаты. Каждая договорённость описана парой deals[j] = [cap, m]:
- если подарок стоит не больше cap, Лео оплачивает его целиком;
- иначе Лео платит cap, а остаток доплачивает Мия.
При договорённости [cap, m] Лео выбирает ровно m разных подарков и хочет, чтобы разность «сколько заплатил Лео минус сколько заплатила Мия» была как можно меньше.
Договорённости рассматриваются независимо друг от друга. Верните массив, где j-й элемент — наименьшая возможная разность для deals[j].costs=[4, 12, 7, 20], deals=[[10, 2], [6, 4]] → [4, 1]
Сделка [10, 2]: Лео выбирает подарки за 4 и 20. За первый он платит 4, за второй — 10, а Мия доплачивает 10; разница 14 − 10 = 4. Сделка [6, 4]: брать приходится всё; Лео платит 4 + 6 + 6 + 6 = 22, Мия — 6 + 1 + 14 = 21, разница 1.
costs=[3, 9], deals=[[2, 1]] → [-5]
Подарок за 9 выгоднее всего: Лео платит 2, Мия — 7, разница 2 − 7 = −5. Ответ может быть отрицательным.
costs.length ≤ 10⁵costs[i] ≤ 10⁹deals.length ≤ 10⁵deals[j] = [cap, m], 1 ≤ cap ≤ 10⁹, 1 ≤ m ≤ costs.lengthcosts=[4, 12, 7, 20], deals=[[10, 2], [6, 4]]
[4, 1]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 95 тестов на сервере, включая скрытые.