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

Учитывая массив 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

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

источник

2017-02-20 cryptomanic

Подумайте об общей сумме и о максимальном значении элемента. – MBo

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

источник

2017-02-20 18:57:42

Мы также должны будем считать MAX, даже если это не так, мы просто вычитаем 1 до начала процедуры. –

Не могли бы вы объяснить, почему это будет работать? – cryptomanic

Если вы придерживаетесь подхода во все времена, выберите два самых высоких значения, вы получите оптимальную сумму. и вы вычитаете 2 из MAX каждый раз, когда вы добавляете 1 к общим точкам. Поэтому единственная проблема, которая может возникнуть, заключается в том, что максимальное значение не может быть полностью уменьшено или MAX является нечетным. Извините, я не знаю, как лучше объяснить это. –

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

ответ

Смежные вопросы