目錄

一：問題描述

二：解決思路

貪心策略（C語言）算法復習總結3——貪心算法-CSDN博客

?三：代碼實現

四：復雜度分析

---

一：問題描述

分發餅干問題是一個經典的可以使用貪心算法解決的問題，問題描述如下：

有一群孩子和一堆餅干，每個孩子都有一個胃口值?g[i]（表示該孩子需要的餅干的最小尺寸才能滿足），每個餅干都有一個尺寸?s[j]。目標是盡可能讓更多的孩子得到滿足，即找到能滿足的孩子的最大數量。也就是說，要將餅干分配給孩子，當且僅當餅干的尺寸大于或等于孩子的胃口值時，這個孩子才能被滿足。（每個孩子最多一塊餅干）

二：解決思路

貪心策略（C語言）算法復習總結3——貪心算法-CSDN博客

貪心策略是優先滿足胃口值小的孩子。因為對于胃口值小的孩子，更容易找到合適尺寸的餅干來滿足他，這樣可以盡量讓更多的孩子得到滿足。具體步驟如下：

1. 對孩子的胃口值數組?g?和餅干尺寸數組?s?分別進行排序（升序）。
2. 用兩個指針分別遍歷孩子數組和餅干數組。
3. 從胃口值最小的孩子開始，嘗試用最小尺寸的餅干去滿足他。如果當前餅干的尺寸大于或等于當前孩子的胃口值，那么這個孩子就被滿足，兩個指針都向后移動一位；如果當前餅干的尺寸小于當前孩子的胃口值，說明這個餅干不能滿足這個孩子，只能嘗試下一個更大尺寸的餅干，即只移動餅干數組的指針。
4. 重復步驟 3，直到遍歷完所有孩子或者所有餅干。

?三：代碼實現

#include <stdio.h>
#include <stdlib.h>// 比較函數，用于 qsort 排序
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 child_index = 0;int cookie_index = 0;// 遍歷孩子和餅干數組while (child_index < gSize && cookie_index < sSize) {if (s[cookie_index] >= g[child_index]) {// 當前餅干能滿足當前孩子，孩子和餅干指針都后移child_index++;cookie_index++;} else {// 當前餅干不能滿足當前孩子，只移動餅干指針cookie_index++;}}return child_index;
}int main() {int g[] = {1, 2, 3};int s[] = {1, 1};int gSize = sizeof(g) / sizeof(g[0]);int sSize = sizeof(s) / sizeof(s[0]);int result = findContentChildren(g, gSize, s, sSize);printf("能滿足的孩子數量是: %d\n", result);return 0;
}

四：復雜度分析

• 時間復雜度：排序操作的時間復雜度為?(O(n log n + m log m))，其中?n?是孩子的數量，m?是餅干的數量。遍歷數組的時間復雜度為?(O(min(n, m)))。所以總的時間復雜度為?(O(n log n + m log m))。
• 空間復雜度：qsort?函數通常需要?(O(log n + log m))?的額外空間，因此總的空間復雜度為?(O(log n + log m))。