Вам задан целочисленный массив \(a_1, a_2, \dots, a_n\) и целое число \(k\).
За один шаг, вы можете
- либо выбрать некоторый индекс \(i\) и уменьшить \(a_i\) на единицу (сделать \(a_i = a_i - 1\));
- либо выбрать два индекса \(i\) и \(j\) и присвоить элементу \(a_i\) значение \(a_j\) (сделать \(a_i = a_j\)).
За какое наименьшее количество шагов вы можете сделать сумму массива \(\sum\limits_{i=1}^{n}{a_i} \le k\)? (В массиве разрешены отрицательные элементы).
Примечание
В первом наборе входных данных, вам нужно уменьшить \(a_1\) \(10\) раз, чтобы получить сумму не более \(k = 10\).
Во втором наборе, сумма массива \(a\) уже не превосходит \(69\), а потому вам не нужно ничего менять.
В третьем наборе, вы можете, например:
- присвоить \(a_4 = a_3 = 1\);
- уменьшить \(a_4\) на единицу, и получить \(a_4 = 0\).
В результате вы получите массив
\([1, 2, 1, 0, 1, 2, 1]\) с суммой, не превосходящей
\(8\), за
\(1 + 1 = 2\) шага.
В четвертом наборе, вы можете, например:
- выбрать \(a_7\) и уменьшить его на один \(3\) раза; вы получите \(a_7 = -2\);
- выбрать \(4\) элемента \(a_6\), \(a_8\), \(a_9\) и \(a_{10}\) и присвоить им значение \(a_7 = -2\).
В результате вы получите массив
\([1, 2, 3, 1, 2, -2, -2, -2, -2, -2]\) с суммой, меньше или равной
\(1\), за
\(3 + 4 = 7\) шагов.