Я вижу хендл satyam343. У меня идут мурашки по телу. Пожалуйста, в этот раз больше задач про медианы. Я их обожаю. Пожалуйста, satyam343, мы верим в тебя.
— Самый большой поклонник satyam343
Вам дан массив \(a\) длины \(n\) и целое число \(k\). Вам также дан бинарный массив \(b\) длины \(n\).
Вы можете выполнить следующую операцию не более \(k\) раз:
- Выбрать индекс \(i\) (\(1 \leq i \leq n\)) такой, что \(b_i = 1\). Установить \(a_i = a_i + 1\) (т.е. увеличить \(a_i\) на \(1\)).
Ваш счёт определяется как \(\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)\), где \(c_i\) обозначает массив длины \(n-1\), который вы получаете, удаляя \(a_i\) из \(a\). Другими словами, ваш счёт — это максимальное значение \(a_i + \operatorname{median}(c_i)\) среди всех \(i\) от \(1\) до \(n\).
Найдите максимальный счёт, который можно получить при оптимальном выполнении операций.
Для произвольного массива \(p\), \(\operatorname{median}(p)\) определяется как \(\left\lfloor \frac{|p|+1}{2} \right\rfloor\)-й элемент в отсортированном \(p\). Например, \(\operatorname{median} \left( [3,2,1,3] \right) = 2\) и \(\operatorname{median} \left( [6,2,4,5,1] \right) = 4\).
Выходные данные
Для каждого набора входных данных выведите на отдельной строке максимальное значение счёт, которое вы можете получить.
Примечание
Для первого набора входных данных оптимально выполнить \(5\) операций над обоими элементами и получить \(a = [8,8]\). Таким образом, максимальная оценка, которую мы можем получить, равна \(\max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16\), так как \(c_1 = [a_2] = [8]\). Можно доказать, что получить больший счёт невозможно.
Для второго набора входных данных вы не можете выполнить операции ни над одним элементом, поэтому \(a\) остается \([3,3,3]\). Таким образом, максимальная оценка, которую мы можем получить, равна \(3 + \operatorname{median}[3, 3] = 6\), так как \(c_1 = [a_2, a_3] = [3, 3]\). Можно доказать, что получить больший счёт невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2 10
3 3
1 1
3 10
3 3 3
0 0 0
4 4
2 1 5 1
0 1 0 1
5 4
7 5 2 5 4
0 0 1 0 1
5 1
5 15 15 2 11
1 0 0 1 1
5 2
10 11 4 10 15
1 1 0 1 0
4 4
1 1 2 5
1 1 0 0
2 1000000000
1000000000 1000000000
1 1
|
16
6
8
13
21
26
8
3000000000
|