#40343: 貪心(含證明)
qerpzzea@gmail.com
(賽希爾 cecill(陳宥穎))
學校
:
高雄市立中正高級中學
編號 : 169400
來源 : [114.40.35.5]
最後登入時間 ：
2024-07-19 09:54:49
步驟
由小到大排序,然後依序加n次,n-1次,n-2次....
證明(權值小的一定要先加)
排第一個,假設為a 會加n次
排第二個,假設為b 會加n-1次
排第k個,假設為z 會加n-k+1次
所以答案會是 a*n+b*(n-1)+c*(n-2)+...z*(n-k+1) 所以要讓總和最小必然要符合 a<=b<=c<=d<=.....
ZeroJudge Forum