Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

2279. Maximum Bags With Full Capacity of Rocks
給你兩個陣列分別表示袋子的容量和石頭數量，現在我們有additionalRocks個石頭可以
放，試問最多可以裝滿幾個袋子。

Example：
Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
Output: 3
Explanation:
編號0、1、3的袋子任選兩個裝石頭加上編號2的袋子已經裝滿，所以最多可裝滿3個。

思路：
1.因為要盡可能的裝滿多個袋子，所以我們可以考慮貪婪演算法。
2.我們對"需要最少石頭就可裝滿"的袋子做貪婪演算法，具體的作法就是算出每個
  袋子缺多少石頭才會裝滿，並且從少到多開始裝，直到每個袋子都檢查過或是已
  經沒石頭可以裝進袋子。
3.我們可以把缺多少石頭的數量排序之後一個一個裝，若need <= additionalRocks 時
  count就加一。

Java Code：
--------------------------------
class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int[] need = new int[n];
        for (int i = 0; i < n; i++) {
            need[i] = capacity[i] - rocks[i];
        }
        Arrays.sort(need);
        int count = 0;
        int j = 0;
        while (j < n && additionalRocks > 0) {
            count += (need[j] <= additionalRocks) ? 1 : 0;
            additionalRocks -= need[j++];
        }
        return count;
    }
}
--------------------------------

--
https://i.imgur.com/uiFto42.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.106.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672104163.A.8DF.html
→ miHoYo: 露西亞可以裝滿幾個袋子
推 sustainer123: 大師
我看到你昨天有在刷題 我不太建議用C刷 全部輪子都要自己造
你要刷可以考慮用C++
※ 編輯: Rushia (1.160.106.12 臺灣), 12/27/2022 09:29:04
推 sustainer123: 我目前只會C 還沒學C++QQ
推 a9486l: 大師
推 pandix: 大師
推 AyuniD: 你可以去看一下 vector 跟 string 之類的東西就好
→ AyuniD: 不然刷題還要自己管理記憶體有點累