#40343: 貪心(含證明)


qerpzzea@gmail.com (賽希爾 cecill(陳宥穎))

School : 高雄市立中正高級中學
ID : 169400
IP address : [163.32.60.236]
Last Login :
2024-11-06 12:35:37
l243. A. 髮廊服務優化問題 -- 110學年度全國資訊學科能力競賽 | From: [118.171.12.114] | Post Date : 2024-05-12 11:26

步驟

由小到大排序,然後依序加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