问题描述:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值
时间: 2024-03-22 22:41:49 浏览: 59
这是一个典型的贪心算法问题,可以采用贪心算法来解决。
首先将孩子的胃口值和饼干的尺寸从小到大排序,然后从小到大依次遍历孩子和饼干,如果当前饼干的尺寸可以满足当前孩子的胃口,就将这个饼干分配给这个孩子,然后继续遍历下一个孩子和饼干。如果当前饼干的尺寸不能满足当前孩子的胃口,则继续遍历下一个饼干,直到找到一个饼干可以满足当前孩子的胃口,或者遍历完所有饼干。
最后统计一下分配了多少个饼干,就是满足的孩子数量的最大值了。
以下是 Python 代码实现:
```python
def findContentChildren(g, s):
g.sort() # 孩子的胃口值排序
s.sort() # 饼干的尺寸排序
i, j = 0, 0 # i 和 j 分别表示当前遍历到的孩子和饼干的下标
count = 0 # 统计满足的孩子数量
while i < len(g) and j < len(s):
if g[i] <= s[j]: # 当前饼干可以满足当前孩子的胃口
count += 1
i += 1
j += 1
else: # 当前饼干不能满足当前孩子的胃口
j += 1
return count
```
例如,对于输入 `g = [1,2,3], s = [1,1]`,调用函数 `findContentChildren(g, s)`,输出为 `1`,表示只有一个孩子可以得到满足。
相关问题
C语言解决,问题描述:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值
同样是一个贪心算法问题,可以采用类似于 Python 的实现方式来解决。
以下是 C 语言代码实现:
```c
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
qsort(g, gSize, sizeof(int), compare); // 孩子的胃口值排序
qsort(s, sSize, sizeof(int), compare); // 饼干的尺寸排序
int i = 0, j = 0; // i 和 j 分别表示当前遍历到的孩子和饼干的下标
int count = 0; // 统计满足的孩子数量
while (i < gSize && j < sSize) {
if (g[i] <= s[j]) { // 当前饼干可以满足当前孩子的胃口
count++;
i++;
j++;
} else { // 当前饼干不能满足当前孩子的胃口
j++;
}
}
return count;
}
```
例如,对于输入 `g = [1,2,3], s = [1,1]`,调用函数 `findContentChildren(g, 3, s, 2)`,输出为 `1`,表示只有一个孩子可以得到满足。
完整C语言解决,问题描述:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值
完整的 C 语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
qsort(g, gSize, sizeof(int), compare); // 孩子的胃口值排序
qsort(s, sSize, sizeof(int), compare); // 饼干的尺寸排序
int i = 0, j = 0; // i 和 j 分别表示当前遍历到的孩子和饼干的下标
int count = 0; // 统计满足的孩子数量
while (i < gSize && j < sSize) {
if (g[i] <= s[j]) { // 当前饼干可以满足当前孩子的胃口
count++;
i++;
j++;
} else { // 当前饼干不能满足当前孩子的胃口
j++;
}
}
return count;
}
int main() {
int g[] = {1, 2, 3};
int s[] = {1, 1};
int gSize = sizeof(g) / sizeof(int);
int sSize = sizeof(s) / sizeof(int);
int result = findContentChildren(g, gSize, s, sSize);
printf("The maximum number of satisfied children is %d\n", result);
return 0;
}
```
运行结果为:
```
The maximum number of satisfied children is 1
```
表示只有一个孩子可以得到满足。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)