1.贪心算法

/*
贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。
*/


//455.分发饼干
/*
分饼干问题
每个孩子都有自己的饥饿度，一堆饼干大小不同，且每个孩子只能分一个饼干，多少孩子可以吃饱
思路是先对vector数组排序，while循环遍历，符合条件 child++ 最后return
*/
int findContentChildren(vector<int> children, vector<int>& cookies) {
    sort(children.begin(), children.end());
    sort(cookies.begin(), cookies.end());
    int child = 0, cookie = 0;
    while (child < children.size() && cookie < cookies.size()) {
        if (children[child] <= cookies[cookie]) ++child;
        ++cookie;
    }
    return child;
}


//135.分发糖果
/*
分发糖果问题 每人必须要有一个，且分数高的要比左右的人的糖果多
思路，先初始化糖果数组为1，正反两遍遍历
*/
int candy(vector<int>& ratings) {
    //思路 正反遍历
    int size = ratings.size();
    if(size < 2){
        return size;
    }
    vector<int> num(size, 1);   //把所有的糖果都初始化为1
    for(int i=1; i<size; i++)
    {
        if(ratings[i]>ratings[i-1]){
            num[i]=num[i-1]+1;          //这里是重点
        }
    }
    for(int i=size-1; i>0; i--)
    {
        if(ratings[i-1]>ratings[i]){
            num[i-1]=max(num[i-1],num[i]+1);        //这里是重点
        }
    }
    return accumulate(num.begin(), num.end(), 0);   //这里也是
}