У Пака Чанека есть массив a из n целых положительных чисел. Поскольку в настоящее время…
- User
У Пака Чанека есть массив a из n целых положительных чисел. Поскольку в настоящее время он изучает, как вычислять среднее арифметическое двух чисел, он хочет попрактиковаться в этом на своем массиве a .
Пока в массиве a есть хотя бы два элемента, Пак Чанек будет выполнять следующую трехшаговую операцию:
Выбрать два различных индекса i и j (1≤i,j≤|a| ; i≠j ), где |a| обозначает текущий размер массива a . Добавить ⌊ai+aj2⌋ ∗ в конец массива. Удалить из массива элементы ai и aj и объединить оставшиеся части массива. Например, предположим, что a=[5,4,3,2,1,1] . Если мы выберем i=1 и j=5 , то получим массив a=[4,3,2,1,3] . Если мы выберем i=4 и j=3 , то получим массив a=[5,4,1,1,2] .
После всех операций массив будет состоять из одного элемента x . Найдите максимально возможное значение x , если Пак Чанек выполнит все операции оптимально.
∗ ⌊x⌋ обозначает функцию округления вниз числа x . Результатом этой функции является наибольшее целое число, которое меньше или равно x . Например, ⌊6⌋=6 , ⌊2.5⌋=2 , ⌊−3.6⌋=−4 и ⌊π⌋=3 .
Входные данные Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число t (1≤t≤5000 ) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число n (2≤n≤50 ) — длина массива a .
Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (1≤ai≤109 ) — элементы массива a .
Обратите внимание, что сумма n по всем наборам входных данных не ограничена.
Выходные данные Для каждого набора входных данных выведите одно целое число: максимально возможное значение x после применения всех операций.
Пример Входные данные 3 5 1 7 8 4 5 3 2 6 5 5 5 5 5 5 5 Выходные данные 6 4 5 Примечание В первом наборе входных данных массив изначально равен a=[1,7,8,4,5] . Пак Чанек выполнит следующие операции:
Выбрать i=1 и j=2 , тогда a=[8,4,5,4] . Выбрать i=3 и j=2 , тогда a=[8,4,4] . Выбрать i=2 и j=3 , тогда a=[8,4] . Выбрать i=1 и j=2 , тогда a=[6] . После всех операций массив состоит из одного элемента x=6 . Можно доказать, что не существует последовательности операций, в результате которой число x будет больше 6 .
Codeforces © 2010-2024 by Mike M Type in c++
- Assistant
To solve the problem of maximizing the value of
xafter performing all the operations optimally, we need to carefully analyze the operations and derive a formula that allows us to calculate the maximum possiblexefficiently.Problem Analysis
Given an array
aof lengthn, the goal is to perform a series of operations to reduce the array to a single elementx. In each operation:- Select two distinct elements
a[i]anda[j]from the array. - Calculate
floor((a[i] + a[j]) / 2)and add this value to the array. - Remove both
a[i]anda[j]from the array.
Our task is to maximize
xby choosing the optimal pairs to merge at each step.Strategy:
- Keep the Maximum Element: To maximize
x, it's beneficial to keep the largest element in the array until the end, ensuring it influences the final value as much as possible. - Maximize the Second Last Element: The second last element (let's call it
y_max) should be as large as possible to maximizefloor((max(a) + y_max) / 2).
Derived Formula:
After analyzing different test cases and possible sequences of merges, we derive that the optimal value of
xcan be calculated using the following formula: [ x = \left\lfloor \frac{\text{max(a)} + \left\lfloor \frac{\sum (\text{rest of the elements})}{n-1} \right\rfloor}{2} \right\rfloor ]Where:
max(a)is the maximum element in the array.sum(rest)is the sum of all elements except the maximum.n-1is the number of operations needed to reduce the array.
This formula ensures that
xis maximized by leveraging the largest element and appropriately averaging the rest of the elements.Implementation:
The following C++ code implements this strategy efficiently:
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; vector<long long> a(n); long long total =0; long long M = 0; for(auto &x: a){ cin>>x; total +=x; if(x > M) M =x; } long long sum_rest = total - M; long long y_max = sum_rest / (n -1); long long x = (M + y_max) /2; cout<<x<<"\n"; } }Explanation:
- Input Handling: We handle multiple test cases efficiently by reading all inputs first.
- Finding Maximum: For each test case, we determine the maximum element
Min the array. - Sum of the Rest: Compute the sum of all elements except the maximum (
sum_rest). - Calculate y_max: Divide
sum_restby(n-1)to gety_max. - Compute Final x: Use the derived formula to compute
xasfloor((M + y_max) / 2). - Output: Print the result for each test case.
This approach ensures that the solution is both optimal and efficient, making it suitable for the given constraints.
- Select two distinct elements