用 C++ 分配 Cookie

假設我們嘗試給孩子們分發一些餅乾。但是，我們應該給每個孩子不超過一塊餅乾。現在，每個孩子 i 都有一個貪婪度 gi，它是孩子會滿足的餅乾的最小大小；每個餅乾 j 有一個大小 sj。當 sj >= gi 時，我們可以把餅乾 j 分配給孩子 i，孩子 i 就會滿足。我們的目標是最大化滿足孩子的數量，並輸出最大數量。

因此，如果輸入類似於 [1,2]，[1,2,3]，則輸出將是 2，有 2 個孩子和 3 塊餅乾。2 個孩子的貪婪度為 1、2。現在我們有 3 塊餅乾，並且它們的大小足夠滿足所有孩子，因此輸出為 2。

為解決這個問題，我們將按照以下步驟操作 -

  • 對陣列 g 進行排序

  • 對陣列 s 進行排序

  • i := 0，j = 0

  • 只要 (i < g 的大小且 j < s 的大小) 執行 -

    • 如果 g[i] <= s[j]，則 -

      • (i 加 1)

    • (j 加 1)

  • 返回 i

示例

為了更好地理解，我們來看一下以下實現 -

 即時演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findContentChildren(vector<int>& g, vector<int>& s) {
      sort(g.begin(), g.end());
      sort(s.begin(), s.end());
      int i = 0, j = 0;
      while (i < g.size() && j < s.size()) {
         if (g[i] <= s[j])
            i++;
            j++;
         }
         return i;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2}, v1 = {1,2,3};
   cout << (ob.findContentChildren(v, v1));
}

輸入

{1,2}, {1,2,3}

輸出

2

更新於：2020 年 6 月 10 日

635 次瀏覽

開啟你的 職業生涯

完成課程並獲得認證

開始
廣告