Giả sử chúng tôi đang cố gắng phân phát một số cookie cho trẻ em. Nhưng, chúng ta nên cho mỗi đứa trẻ ăn nhiều nhất một cái bánh quy. Bây giờ mỗi đứa trẻ tôi có một yếu tố tham lam gi, là kích thước tối thiểu của một cookie mà đứa trẻ sẽ hài lòng; và mỗi cookie j có kích thước sj. Khi sj> =gi, ta có thể gán cookie j cho con i, và con tôi sẽ bằng lòng. Mục tiêu của chúng tôi là tối đa hóa số lượng nội dung con và xuất ra số lượng tối đa.
Vì vậy, nếu đầu vào là [1,2], [1,2,3], thì đầu ra sẽ là 2, có 2 con và 3 cookie. Hệ số tham của 2 trẻ em là 1, 2. Bây giờ chúng ta có 3 chiếc bánh quy và kích thước của chúng đủ lớn để chứa tất cả các trẻ em, vì vậy sản lượng là 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp mảng g
-
sắp xếp mảng s
-
i:=0, j =0
-
while (i
-
nếu g [i] <=s [j], thì -
-
(tăng tôi lên 1)
-
-
(tăng j lên 1)
-
-
trả lại tôi
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
{1,2}, {1,2,3} Đầu ra
2