首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> 更多程式語言 >> 程式設計疑難解答

貪心算法:超級移動充電器給手機充電最大化滿電數量

     編輯:程式設計疑難解答

問題描述

N 部手機,第 i 部電量 p[i]%,充電器總電量 M%。每部手機充至 100% 視為滿電。求最多能充滿幾部手機。

樣例:

3 10
100 99 90  -> 輸出 2 (99需1%, 90需10%, 共11%超過10, 故只能充99和100已滿電不算)
3 1000
0 0 0    -> 輸出 3

貪心策略

  1. 計算每部手機所需電量:need = 100 - p[i](已滿電 need=0)。
  2. 將 need 從小到大排序。
  3. 依次累加 need,直到總和超過 M,已累加個數即為答案。

時間複雜度 O(N log N)。完整代碼參考:博客

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved