ALGO-34 紀(jì)念品分組（貪心算法+排序）

題目描述 元旦快到了，校學(xué)生會(huì)讓樂(lè)樂(lè)負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。為使得參加晚會(huì)的同學(xué)所獲得的紀(jì)念品價(jià)值相對(duì)均衡，他要把購(gòu)來(lái)的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組，但每組最多只能包括兩件紀(jì)念品，并且每組紀(jì)念品的價(jià)格之和不能超過(guò)一個(gè)給定的整數(shù)。為了保證在盡量短的時(shí)間內(nèi)發(fā)完所有紀(jì)念品，樂(lè)樂(lè)希望分組的數(shù)目最少。

你的任務(wù)是寫一個(gè)程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目。

輸入描述 Input Description 包含n+2行：

第1行包括一個(gè)整數(shù)w，為每組紀(jì)念品價(jià)格之和的上限。

第2行為一個(gè)整數(shù)n，表示購(gòu)來(lái)的紀(jì)念品的總件數(shù)。

第3~n+2行每行包含一個(gè)正整數(shù)pi (5 <= pi <= w)，表示所對(duì)應(yīng)紀(jì)念品的價(jià)格。

輸出描述 僅一行，包含一個(gè)整數(shù)，即最少的分組數(shù)目。

樣例輸入 Sample Input 100

9

90

20

20

30

50

60

70

80

90

樣例輸出 Sample Output 6

數(shù)據(jù)范圍及提示 Data Size & Hint 50%的數(shù)據(jù)滿足：1 <= n <= 15

100%的數(shù)據(jù)滿足：1 <= n <= 30000, 80 <= w <= 200

分析：排序+貪心。先從小到大排序，i、j指針?lè)謩e從左到右、從右到左遍歷。如果a[i]+a[j] <= w，那么把這兩個(gè)物品都放入同一組，并且同時(shí)移動(dòng)指針；否則，只能把j所指向的物品放入單獨(dú)的一個(gè)組，移動(dòng)j指針…直到i j把所有物品都遍歷完~分析下貪心算法的可行性：如果j物品和i物品加起來(lái)超過(guò)了w，因?yàn)閖物品比j+1處的物品價(jià)值小，那么如果i不能滿足加起來(lái)的條件，而i-1能滿足該條件，是否會(huì)影響貪心算法的結(jié)果呢？如果讓j和i-1去組合，對(duì)于j+1，因?yàn)閮r(jià)值比j更大，所以就更放不進(jìn)i了，所以即使交換組合方式還是不影響構(gòu)成的組數(shù)的~至于為什么循環(huán)的條件是i <= j，當(dāng)i<j的時(shí)候，假設(shè)i j已經(jīng)相鄰，那么此時(shí)還能再比較一次i+j能否滿足構(gòu)成一組的條件，如果滿足就會(huì)把它們放到一組，之后i j指針同時(shí)移動(dòng)后i>j不能夠滿足進(jìn)入循環(huán)的條件了；如果不滿足把它們放入一組，那么j放入一組后j移動(dòng)指針，使i == j，繼續(xù)進(jìn)入循環(huán)；當(dāng)i == j的時(shí)候，因?yàn)檫@個(gè)單獨(dú)的物品已經(jīng)沒(méi)有可以組合的物品剩余了，所以此時(shí)還要進(jìn)入循環(huán)進(jìn)行一次 cnt++ 的計(jì)數(shù)操作~//這就是while(i <= j)的解釋~~~

#include <iostream>

#include <algorithm>