【贪心】 LeetCode455. 分发饼干

短命女 2022-12-03 13:20 158阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]

### 解答 ###

#include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <algorithm>
    #include <cassert>
    
    // 455. Assign Cookies
    
    // 贪心算法，求得局部最优解。
    int findContentChildren(std::vector<int>& g, std::vector<int>& s) { 
      // 将两个序列排序。
      std::sort(g.begin(), g.end());
      std::sort(s.begin(), s.end());
    
      std::size_t greed_len = g.size();
      std::size_t cookie_len = s.size();
      std::size_t greed_pos = 0;
      std::size_t cookie_pos = 0;
    
      while (greed_pos < greed_len && cookie_pos < cookie_len) { 
        // 每个孩子都获得刚刚好满足他们的糖果，然后更大的糖果就能满足需求更大的孩子。
        // 从而不造成大糖果的浪费。如果大糖果给了需求小的孩子，那么就只剩下小的糖果，
        // 而小的糖果并不能满足需求大的孩子。
        if (g[greed_pos] <= s[cookie_pos]) { 
          ++greed_pos;
        }
        ++cookie_pos;
      }
    
      return greed_pos;
    }
    
    int main() { 
      std::vector<int> g = {  2, 4, 5 };
      std::vector<int> s = {  1, 7, 2, 6, 3 };
    
      std::cout << findContentChildren(g, s) << std::endl;
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/85757e9ce1534ca4988f7d35ac396ecc.png

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关 455. 分发饼干

参考链接：https://leetcode.cn/problems/assign-cookies/description/

本是古典何须时尚/ 2024年05月24日 01:27/ 0 赞/ 65 阅读

相关 455. 分发饼干

455. 分发饼干 > 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 > 对每个孩子 i，都有一个胃口值 g\[i\]，这是能

Love The Way You Lie/ 2024年04月06日 12:51/ 0 赞/ 58 阅读

相关贪心算法-leetcode：455.分发饼干

问题描述假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的

曾经终败给现在/ 2024年03月29日 16:23/ 0 赞/ 55 阅读

相关 LeetCode_贪心算法_简单_455.分发饼干

目录 1.题目 2.思路 3.代码实现（Java） 1.题目假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼

骑猪看日落/ 2023年10月09日 20:28/ 0 赞/ 56 阅读

相关 LeetCoded贪心算法系列——455.分发饼干

一、题目描述： [455. 分发饼干![icon-default.png_t_M5H6][]https://leetcode.cn/problems/assign-coo

Love The Way You Lie/ 2023年10月03日 19:29/ 0 赞/ 10 阅读

相关 leetcode 455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块

布满荆棘的人生/ 2023年07月04日 14:22/ 0 赞/ 9 阅读

相关【贪心】 LeetCode455. 分发饼干

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

短命女/ 2022年12月03日 13:20/ 0 赞/ 159 阅读

相关 455. 分发饼干

> 每个孩子最多只能给一块饼干。 > > 对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\]

我会带着你远行/ 2022年10月05日 03:58/ 0 赞/ 188 阅读

相关 leetcode 455 分发饼干

前言题目：[455. 分发饼干][455.] 参考题解：[分发饼干-代码随想录][-] -------------------- 提交代码比较简单的贪心事

迈不过友情╰/ 2022年08月28日 10:41/ 0 赞/ 154 阅读

相关 LeetCode 455.分发饼干（C++）

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块

灰太狼/ 2021年12月16日 17:43/ 0 赞/ 317 阅读