如何最大限度地提高總積分？

給定一個數組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。如果滿足這個條件，那麼我們必須從BIG和MAX中減去1，直到BIG小於或等於MAX/2。

來源

2017-02-20 18:57:42

我們也必須假定MAX即使不是那麼我們在開始程序之前簡單地減去1。 –

你能解釋爲什麼這會起作用嗎？ – cryptomanic

如果你採取這種方式來選擇兩個最高值，你會得到最佳總和。並且每次將總數加1時，您從MAX中減去2。所以唯一可能發生的問題是如果最高值不能完全降低，或者MAX是奇數。對不起，我不知道如何更好地解釋這一點。 –

如何最大限度地提高總積分？

回答

相關問題