当前位置：首页 > article >正文

代码随想录算法训练营第二十七天-贪心算法-455. 分发饼干

article 2025/1/9 6:12:11

解题思路从最大的饼干开始找出胃口最大的孩子来满足
如果可以满足，再找第二大饼干，和可以满足下一个胃口最大的孩子
所以一开始要对孩子胃口与饼干的数组进行从大到小排序
再倒序查找可以满足孩子胃口的最大饼干，找到这样的饼干后，再用下一个最大的饼干找下一个可以满足孩子的胃口

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        int count = 0;
        int s_index = s.size() - 1;
        for (int i = g.size() - 1; i >= 0; --i) {
            if (s_index >= 0 && s.at(s_index) >= g.at(i)) {
                ++count;
                --s_index;
            }
        }
        return count;
    }
};

int main()
{
    std::vector<int> g {1, 2};
    std::vector<int> s1 {1, 2, 3};
    Solution s;
    std::cout << s.findContentChildren(g, s1) << std::endl;
    return 0;
}