Задача №115388. Покупка колы
Есть вендинговый аппарат, в котором продаётся кола. Всего в аппарате есть \(n\) ячеек. Вы знаете, что изначально в ячейке \(i\) находятся \(a_i\) банок колы. Также в аппарате есть \(n\) кнопок, каждая кнопка соответствует какой-то ячейке, при этом каждой ячейке соответствует ровно одна кнопка. К сожалению, обозначения на кнопках стёрлись, поэтому вы не знаете , какая кнопка соответствует какой ячейке.
Когда вы нажимаете на кнопку, соответствующую ячейке \(i\), из \(i\)-й ячейки выпадает одна банка колы, если они там ещё остались. После нажатия банка выпадает так быстро, что отследить, из какой именно ячейки она выпала, невозможно. Содержимое ячеек закрыто от ваших глаз, поэтому вы не можете в реальном времени видеть, сколько банок осталось в каждой из ячеек, единственное, что вам известно, это изначальные количества банок в ячейках: \(a_1, a_2, \ldots, a_n\).
После каждого нажатия вы узнаете, выпала ли вам банка колы из ячейки, и забираете её себе, если да.
Какое минимальное количество нажатий на кнопки нужно произвести, чтобы гарантированно получить хотя бы \(k\) банок колы? Вы можете адаптировать свою стратегию по ходу нажатий, основываясь на том, выпала вам банка или нет. Гарантируется, что всего в аппарате есть хотя бы \(k\) банок колы, иными словами, \(k \leq a_1 + a_2 + \ldots + a_n\).
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \leq k \leq 10^9\)) — количество ячеек в аппарате и необходимое количество банок колы.
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — количества банок в ячейках.
Гарантируется, что \(k \leq a_1 + a_2 + \ldots + a_n\), то есть всего в аппарате есть хотя бы \(k\) банок колы.
Гарантируется, что сумма значений \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — минимальное количество нажатий на кнопки, которое нужно сделать, чтобы гарантированно получить хотя бы \(k\) банок колы.
В первом наборе входных данных одна из оптимальных стратегий такова:
Нажимаем на первую кнопку дважды. Первое нажатие гарантированно выдаст банку колы. Далее есть два варианта:
-
Если второе нажатие не выдало банку колы, мы знаем, что эта кнопка обязательно соответствует второй ячейке, так как \(a_2 = 1\) и \(a_1 > 1\), \(a_3 > 1\). Тогда мы можем нажать на вторую кнопку два раза, а на третью кнопку один раз, и так как \(a_1 \geq 2\) и \(a_3 \geq 2\): мы гарантированно получим три банки колы за эти три нажатия. Итого за \(5\) нажатий мы получим \(4\) банки колы.
-
Если второе нажатие выдало банку колы, мы можем сделать одно нажатие на вторую кнопку и одно нажатие на третью кнопку. Каждое из этих нажатий гарантированно выдаст нам банку колы. Итого за \(4\) нажатия мы получим \(4\) банки колы.
Можно показать, что за \(4\) нажатия невозможно гарантировать получение \(4\) банок колы, поэтому ответ \(5\).
3 3 4 2 1 3 10 50 1 1 3 8 8 9 12 13 27 27 2 1000000000 1000000000 500000000
5 53 1000000000