C++에서 쿠키 할당

몇몇 쿠키를 아이들에게 배포하려고 한다고 가정해 봅시다. 그러나 우리는 각 어린이에게 최대 하나의 쿠키를 제공해야 합니다. 이제 각 아이 i는 아이가 만족할 쿠키의 최소 크기인 탐욕 요소 gi를 가지고 있습니다. 각 쿠키 j는 sj 크기를 갖습니다. sj>=gi일 때 쿠키 j를 자식 i에 할당할 수 있고 자식 i는 만족할 것입니다. 우리의 목표는 콘텐츠 자식의 수를 최대화하고 최대 수를 출력하는 것입니다.

따라서 입력이 [1,2], [1,2,3]과 같으면 출력은 2이고 2개의 자식과 3개의 쿠키가 있습니다. 2명의 자식의 탐욕 요소는 1, 2입니다. 이제 3개의 쿠키가 있고 쿠키의 크기는 모든 자식을 만족시킬 만큼 크므로 출력은 2입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 g
정렬
배열 정렬
나는 :=0, j =0
동안 (i
- 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}