C++刷leetcode（455. 分发饼干）【贪心思想】

糖逗

题目描述：

1. 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
   
2. 
   
3. 注意：
   
4. 
   
5. 你可以假设胃口值为正。
   
6. 一个小朋友最多只能拥有一块饼干。
   
7. 
   
8. 示例 1:
   
9. 
   
10. 输入: [1,2,3], [1,1]
    
11. 
    
12. 输出: 1
    
13. 
    
14. 解释:
    
15. 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
    
16. 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
    
17. 所以你应该输出1。
    
18. 示例 2:
    
19. 
    
20. 输入: [1,2], [1,2,3]
    
21. 
    
22. 输出: 2
    
23. 
    
24. 解释:
    
25. 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
    
26. 你拥有的饼干数量和尺寸都足以让所有孩子满足。
    
27. 所以你应该输出2.
    
28. 
    
29. 来源：力扣（LeetCode）
    
30. 链接：https://leetcode-cn.com/problems/assign-cookies
    
31. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int solution(vector<int>& g, vector<int>& s) {
   
8.     sort(g.begin(), g.end());
   
9.     sort(s.begin(), s.end());
   
10. 
    
11.     int len1 = g.size(), len2 = s.size();
    
12.     int temp = 0;
    
13.     int res = 0;
    
14.     for(int i = 0; i < len1; i++){
    
15.         if(temp >= len2) break;
    
16.         if(g[i] <= s[temp]){
    
17.             res++;
    
18.             temp ++;
    
19.         }
    
20.         else{
    
21.             while(temp < len2 &&g[i] > s[temp]){
    
22.                 temp++;
    
23.             }
    
24.             if(temp == len2)return res;//未找到
    
25.             res++;
    
26.             temp++;
    
27.         }
    
28.     }
    
29.     return res;
    
30. }
    
31. 
    
32. int main(void){
    
33.         vector<int> input1, input2;
    
34.         int number;
    
35.         while(cin >> number){
    
36.                 input1.push_back(number);
    
37.         }
    
38.         cin.clear();
    
39.         while(cin >> number){
    
40.                 input2.push_back(number);
    
41.         }
    
42.         cin.clear();
    
43.         cout << solution(input1, input2) << endl;
    
44.         return 0;
    
45. }

复制代码

糖逗

贪心思想