当前位置：首页 > article >正文

[LeetCode-455]基于贪心算法的分发饼干问题的求解（C语言版）

article 2024/10/30 23:04:49

题目出处：LeetCode

题目序号：455. 分发饼干

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

程序清单

#include <stdio.h>

// 冒泡排序
void bubble_sort(int *a, int length) {
int i, j, temp;
for (i = 0; i < length - 1; i++){
for (j = 0; j < length - 1 - i; j++){
   if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
       }
   }
}

// 分发饼干
int SplitBiscuit(int *s, int *g,int m, int n) {
   int i = 0;                   // i 是饼干形状数组位标索引
   int j = 0;                   // j 是孩子胃口数组位标索引
   bubble_sort(s, m);           // 对饼干形状数组排序
   bubble_sort(g, n);           // 对孩子胃口数组排序
   for(i=0; i<m; i++) {
       if(j<n && s[i]>=g[j]){
           j++;               // 如果可分发，位标移向下一个，否则不移动孩子
       }
   }
   return j;
}

int main() {
   int m,n,i;
   printf("请输入饼干的数量：\n");
   scanf("%d",&m);
   int s[m];
   printf("请输入每块饼干的尺寸大小：\n");
   for (i=0; i<m; i++) {
       scanf("%d",&s[i]);
   }
   printf("请输入孩子的数量：\n");
   scanf("%d",&n);
   int g[m];
   printf("请输入每个孩子的胃口大小：\n");
   for (i=0; i<n; i++) {
       scanf("%d",&g[i]);
   }
   printf("一共可以满足 %d 个孩子的需求。\n",SplitBiscuit(s, g, m, n));
   return 0;
}