Leetcode455. 分發餅幹（C語言）

算法-貪心思想：算法與資料結構參考

題目：

假設你是一位很棒的家長，想要給你的孩子們一些小餅幹。但是，每個孩子最多隻能給一塊餅幹。

每個孩子 i 都有一個胃口值 gi ，這是能滿足孩子胃口的餅幹最小尺寸；

每塊餅幹 j ，都有一個尺寸 sj 。

如果 sj >= gi ，可将餅幹 j 配置設定給孩子 i ，孩子會得到滿足。盡可能滿足越多數量的孩子，并輸出這個最大數值。例:

輸入: [1,2], [1,2,3]

輸出: 2

解釋:

你有兩個孩子和三塊小餅幹，2個孩子的胃口值分别是1,2。

你擁有的餅幹數量和尺寸都足以讓所有孩子滿足。是以輸出2。

思路：

先分别按孩子胃口給孩子排序，餅幹大小給餅幹排序。

若餅幹j能滿足孩子i，則count計數，否則餅幹後移一個繼續比較（更大尺寸）。

可直接調用c語言自帶的快速排序函數qsort：

函數聲明：

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void , const void))

參數：

base-- 指向要排序的數組的第一個元素的指針。

nitems-- 由 base 指向的數組中元素的個數。

size-- 數組中每個元素的大小，以位元組為機關。

compar-- 用來比較兩個元素的函數，即函數指針（回調函數）

compar參數指向一個比較兩個元素的函數，必須是const void *型，compar實質為函數指針，這裡稱它所指向的函數也為compar。在compar函數内部會将const void *型轉換成實際類型。
int compar(const void *p1, const void *p2);
　　如果compar傳回值小于0（< 0），那麼p1所指向元素會被排在p2所指向元素的左面；
　　如果compar傳回值等于0（= 0），那麼p1所指向元素與p2所指向元素的順序不确定；
　　如果compar傳回值大于0（> 0），那麼p1所指向元素會被排在p2所指向元素的右面。
           

代碼：

int cmp ( 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(g[0]),cmp);
    qsort(s,sSize,sizeof(s[0]),cmp);
    
    int i=0,j=0,count=0;
    while(i<gSize && j<sSize){
        if(g[i]>s[j])   j++;
        else{
            count++;
            i++;
            j++;
        }
    }
    
    return count;
}