分发饼干

向右看齐 2022-04-25 02:38 223阅读 0赞

### 问题描述： ###

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

**注意：**

你可以假设胃口值为正。  
 一个小朋友最多只能拥有一块饼干。

### 示例描述： ###

**示例 1:**

**输入:** \[1,2,3\], \[1,1\]  
 **输出:** 1  
 **解释:**  
 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。  
 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。  
 所以你应该输出1。

**示例 2:**

**输入:** \[1,2\], \[1,2,3\]  
 **输出:** 2  
 **解释:**  
 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。  
 你拥有的饼干数量和尺寸都足以让所有孩子满足。  
 所以你应该输出2.

### 解题思路 ###

因为最小胃口的孩子最容易得到满足的，因此要先考虑胃口最小孩子。拿最小的饼干要先去满足胃口最小的孩子，如果无法满足要去拿第二小的饼干去满足，如果满足了就拿第二小的饼干去满足胃口第二小的孩子，满足的孩子数加一。以此类推，直到胃口最大的孩子被满足或最大尺寸的饼干用完结束，贪心的思想。

### 代码展示 ###

C++版

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    //贪心的思想：用尽量小的饼干去满足小需求的孩子，所以先进行排序
    int findContentChildren(vector<int> &g, vector<int> &s)
    {
        int childnum = 0;
        int cookienum = 0;
        sort(g.begin(), g.end()); //先将饼干 和 孩子所需大小都排序
        sort(s.begin(), s.end());
        while (childnum < g.size() && cookienum < s.size())
        { //当其中一个遍历完就结束
            if (g[childnum] <= s[cookienum])
            { //当用当前饼干可以满足当前孩子的需求，可以满足的孩子数量+1
                childnum++;
            }
            cookienum++; // 饼干只可以用一次，因为饼干如果小的话，就是无法满足被抛弃，满足的话就是被用了
        }
        return childnum;
    }
    
    int main()
    {
        int child,cookie;
        vector<int>vecChild;
        vector<int>vecCookie;
    
        while(cin>>child)    //输入孩子的胃口
        {
            vecChild.push_back(child);
            char c = cin.get();
    		if(c == '\n')
    			break;
        }
    
        while(cin>>cookie)   //输入饼干的尺寸
        {
            vecCookie.push_back(cookie);
            char c = cin.get();
    		if(c == '\n')
    			break;
        }
        int result = findContentChildren(vecChild,vecCookie);
        cout<<result<<endl;
        return 0;
    }

Java版

import java.util.Arrays;
    import java.util.Scanner;
    
    public class FindContentChildren {
    	//主函数用于获取孩子和饼干的数组并且输出结果
    	public static void main(String[] args) {
    		int a[]=scanner();
    		int b[]=scanner();
    		int result=findContentChildren(a,b);
    		System.out.println(result);
    	}
    		 
    	//接收输入各个孩子胃口的数组 和 各个饼干尺寸的数组
    	public static int[] scanner() {
    		Scanner scan = new Scanner(System.in);
    		String str;
    		str = scan.nextLine();
    	    String[] arr  = str.split(" ");
    	    int[] b = new int[arr.length];
    	    for(int j = 0; j<b.length;j++) 
    	    	b[j] = Integer.parseInt(arr[j]);
    		return b;	
    	}
    	
    	//child孩子数组 cookie饼干数组 childnum满足的孩子的数量 cookienum饼干的数量
    	public static int findContentChildren(int child[],int cookie[]){
    		//贪心的思想：用尽量小的饼干去满足小需求的孩子，所以先进行排序
    		int childnum=0;
    		int cookienum=0;
    		Arrays.sort(child);
    		Arrays.sort(cookie);
    		//当其中一个遍历完就结束
    		while(childnum<child.length&&cookienum<cookie.length){
    			if(child[childnum]<=cookie[cookienum]){
    				//当用当前饼干可以满足当前孩子的需求，可以满足的孩子数量+1
    				childnum++;
    			}
    			 // 饼干只可以用一次，因为饼干如果小的话，就是无法满足被抛弃，满足的话就是被用了
    			cookienum++;
    		}
    		return childnum;
    	}
    
    }

### 补充 ###

比较详细的注释已经标在代码里面了，代码里还提供了一种从键盘中读取数组的方法供使用。