2279. Maximum Bags With Full Capacity of Rocks

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Greedy、Sorting

一、題目

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.
Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.

Example 1:

  • Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
  • Output: 3
  • Explanation: Place 1 rock in bag 0 and 1 rock in bag 1.
    The number of rocks in each bag are now [2,3,4,4].
    Bags 0, 1, and 2 have full capacity.
    There are 3 bags at full capacity, so we return 3.
    It can be shown that it is not possible to have more than 3 bags at full capacity.
    Note that there may be other ways of placing the rocks that result in an answer of 3.

Example 2:

  • Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
  • Output: 3
  • Explanation: Place 8 rocks in bag 0 and 2 rocks in bag 2.
    The number of rocks in each bag are now [10,2,2].
    Bags 0, 1, and 2 have full capacity.
    There are 3 bags at full capacity, so we return 3.
    It can be shown that it is not possible to have more than 3 bags at full capacity.
    Note that we did not use all of the additional rocks.

Constraints:

  • n == capacity.length == rocks.length
  • 1 <= n <= 5 * 10^4
  • 1 <= capacity[i] <= 10^9
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 10^9

二、分析

  • 思考如何用現有的 additionalRocks 填滿最多個已裝了 rocks[i] 個石頭且原本容量為 capacity[i] 的背包。
  • 用 greedy 的思維來思考，首先先填滿需要最少額外石頭的背包，依序填到沒有額外的石頭，那麼便可以得到最多個已裝滿的背包。
  • 也就是說先求 capacity[i] - rocks[i]，再將之排序後，逐一累加，直到超過 additionalRocks。

三、解題

1. Greedy

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
    vector<int>& need = capacity;               // 借用 capacity 的空間，減少額外空間使用
    for (int i = 0; i < capacity.size(); i++) {
        need[i] -= rocks[i];                    // 算出每個背包還需多少個石頭才裝滿
    }
    sort(need.begin(), need.end());             // 裝背包依所需石頭數從小到大排序
    int cnt = 0;
    int used = 0;
    while (cnt < capacity.size()) {
        used += need[cnt];                      // 算出累加所需的石頭數
        if (used > additionalRocks) break;      // 超出 additionalRocks 則跳出
        cnt++;                                  // 沒超出則滿足的背包數加 1
    }
    return cnt;
}

回目錄 Catalog