Как максимизировать общие баллы?

Question

Учитывая массив A [1: N]. Каждый элемент массива неотрицателен. Операция разрешена: выберите два элемента массива (значение обоих элементов должно быть по крайней мере 1) и уменьшите оба элемента на 1. Таким образом, мы заработаем 1 балл. Каковы максимальные моменты, которые можно получить?

Пример:

A[1:3] = 1 1 2 
After step 1: 0 1 1 
After step 2: 0 0 0 
Maximum points = 2 

перебором подход:

total_points <- 0 
while value of atleast two elements of A is greater than 0: 
     subtract 1 from both 
     total_points <- total_points + 1 
return total_points 

Как улучшить подход? Пожалуйста помоги.

Answer 1

Прежде всего, вы можете суммировать все значения. Позволяет называть это MAX. Затем вы проверяете, есть ли один элемент, который содержит больше MAX/2, позволяет вызвать этот элемент BIG. Если это условие не выполнено, то ответ должен быть просто MAX/2. Если это условие выполнено, мы должны вычесть 1 из BIG и MAX, пока BIG не будет меньше или равен MAX/2.