贪心的算法笔记(1)——【分糖果】
分糖果
题目:
已知一些孩子和一些糖果,每个孩子有需求因子g,每个糖果有大小s,当 某个糖果的大小s >= 某个孩子的需求因子g时,代表该糖果可以满足该孩子;求使用这 些糖果,最多能满足多少孩子?(注意,某个孩子最多只能用1个糖果满足) 例如,需求因子数组g = [5, 10, 2, 9, 15, 9];糖果大小数组s = [6, 1, 20, 3, 8];最多可以满足3个孩子。
解题图解:
题解代码:
// 1.分糖果.cpp #include <iostream> #include<vector> #include<algorithm> using namespace std; class MyClass { public: int getMinResult(vector<int>& g, vector<int>& s) { //进行排序 sort(g.begin(), g.end()); sort(s.begin(), s.end()); int child = 0; int cookie = 0; while (child < g.size() && cookie < s.size()) { if (s[cookie] >= g[child]) { child++; } cookie++; } return child; } private: }; int main() { vector<int> g; vector<int> s; g.push_back(5); g.push_back(10); g.push_back(2); g.push_back(9); g.push_back(15); g.push_back(9); s.push_back(6); s.push_back(1); s.push_back(20); s.push_back(3); s.push_back(8); MyClass cls; int n =cls.getMinResult(g, s); cout << n << endl; }