即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Leetcode:455. Assign Cookies

编程语言 u013935580 12℃ 0评论

代码:

    class Solution {


public:


    int findContentChildren(vector& g, vector& s) {


        sort(g.begin(),g.end());


        sort(s.begin(),s.end());


        


        int num=0;


        int pass=0;


        vector::iterator tag=g.begin();


        vector::iterator i;


        


        for(i=s.begin();i!=s.end();i++){


            if(pass==0){


                if(*i>=*tag){


                    if(num==g.size()-1){


                        pass=1;


                        num++;


                    }


                    else{


                       num++;


                       tag++;


                    }


                 }


            


            }


        }


        


        return num;


        


    }


};


原理:

   (1)把两组数组排序(升序),设置满足个数为0

   (2)根据贪婪选择原则,当前size最小的饼如果不能满足当前greedy最小的孩子,那么当前size最小的饼不能满足所有的孩子

   (3)从饼数组第一个开始遍历,如果当前饼可以满足孩子数组的第一个,那么满足个数加一,然后饼数组和孩子数组都往后移一位

             如果不能满足,满足个数不变,那么饼数组往后移一位

            直到遍历完所有的饼数组或者孩子数组为止

    (4)当前满足个数就是目前所有的饼能够满足的最多的孩子的个数

转载请注明:CodingBlog » Leetcode:455. Assign Cookies

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情