2017-02-20 29 views
1

給定一個數組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 

如何改善的方法?請幫忙。

+1

想想整體總和和最大元素值。 – MBo

回答

1

首先你可以總結所有的值。讓我們打電話給MAX。 然後你檢查是否有一個元素保存超過MAX/2,讓我們稱這個元素爲BIG。 如果這個條件不符合,那麼答案應該只是MAX/2。 如果滿足這個條件,那麼我們必須從BIG和MAX中減去1,直到BIG小於或等於MAX/2。

+0

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

+1

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

+0

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

相關問題