轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年3月6日 星期四

STEP5::Problem 0022 : 掉落的橘子

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0022
題目要我們找出最佳的位置上,在cost範圍內能加入幾個點,每加入一個點就會花費d,d是點和最佳位置的距離。

基本上一段區間中的最佳位置一定是這段區間的中位數(項數是偶數個了話中間兩個數任意一個都成立),因為中位數左右點的數量一樣,計算距離不會重疊到(左右抵銷)。
總之就是一直從右邊push點近來,並更新中位數的位置,順便更新總cost(左邊有N個點就加上N乘以中位數移動的距離,右邊有M個點就扣掉M乘以中位數移動的距離)。如果cost小於或等於題目給的上限,就記錄現在總共有幾個點(紀錄最大值),如果cost超過就從左邊pop掉點,並更新中位數和總cost,這樣O(N)可以做完。
要注意檢查cost和更新中位數的順序和迴圈的上限。