1.问题描述:现有四块不同大小的饼干,分给四个胃口大小不同的小孩子,请问最多能分给多少个小孩?

例如:以下数组g代表四个小孩的胃口,数组s为饼干大小:

g(表示胃口大小)	7	1	2	10
s(表示饼干大小)	1	3	9	5

首先提出一个问题:看到饼干和胃口的大小之后,我们想,能否将大小为9的饼干分给胃口为1的小朋友呢?

答:从题面上来看当然没有问题,但是,我们这题主要是求最多小孩能吃到的分法!!!

这时就提出贪心法的概念了:

贪心法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心法并不保证总是能得到全局最优解，但对很多问题它能产生令人满意的近似解，并且贪心法实现简单，效率较高。

总结:寻找到局部最优解!

那么对于此题而言,一定要将大饼干尽可能的分给大胃口的孩子!

这就是我们此题解题的基本出发点了.

2.那么问题又来了:按照上面的数组来说顺序是乱的呀!

PS:所以我们要用STL容器中的sort函数,没有学过vector动态数组的可以去弥补一下哦

用sort函数升序之后:我们就可以遍历胃口,把尽可能大的饼干给大胃口的孩子吃了

g(胃口)	1	2	7	10
s(饼干)	1	3	5	9

3.话不多说,上代码和解析:

result:用于存储饼干分出去的数量;

index索引:初始时指向已经升序完成的饼干s的尾部(因为我们需要先将最大的饼干尽可能的分给胃口较大的学生,如果最大的饼干都满足不了最小的胃口,那么result自然是为0的)

重点问题:为什么用for控制胃口,用index指向饼干!!!!!!!!!!!!

                答:对于胃口的for循环而言:下标i是固定移动的,不管index的饼干满不满足,i在语句执行完成之后总是自减的(不论是否满足if里的判断)-----举个例子:最大的饼干都满足不了最小的胃口,那么result自然是为0的,因为i一直循环到为0才停止. 

而if里面的下标index只有满足将最大的饼干分出去之后再自减,再分第二大的饼干,以此类推!

#include <bits/stdc++.h> //万能头文件,包括大部分库函数
using namespace std;
int findContentChildren(vector<int>&g,vector<int>&s){ //&g和s是对main函数直接修改原始数据
	int result=0;
	sort(g.begin(),g.end()); //对STL容器的sort升序操作
	sort(s.begin(),s.end());
	int index=s.size()-1; 
	for(int i=g.size()-1;i>=0;i--){
		if(index>=0 && s[index]>=g[i]){
			result++;
			index--;
		}
	}
	return result;
} 

int main(){
	vector<int> g = {7, 1, 2, 10};   
    vector<int> s = {1, 3, 9, 5};
	int result=findContentChildren(g,s);
	cout <<result;
	return 0;
}

分饼干问题已经解决啦!

请给up关注点点吧,后期也会做递归,回溯,动态规划等基本算法

都是up的自己见解,有什么不正确还请指正