1.引言

ok啊，拖更這么長時間也是沒有壓力（doge）

不說啥，直接進入正題。

2.概念

這個貪心算法呢，看名字就知道，不就是每個步驟都挑最好的嘛，有啥難的。

這么說的話......其實確實，你如果真的能很快找出貪心策略那就可以這么說，但還是那句話，策略怎么找是個問題。

講這么多，還沒講一下定義（雖然不講感覺也能猜出來）：

貪心算法就是在特定問題中每一次計算都做出最好的選擇，舉個例子：

本蒟蒻去商店買東西，這商店呢，規矩是每天商品的價格都是原來的2倍（這商店不得不說是真敢這么加價啊），且商品不繼續進貨（怎么開下去的）。而我這個蒟蒻呢，很有錢，但很吝嗇，想要花最少的錢把商店里的東西全買一遍，于是本蒟蒻就開始定制一個計劃。

這個商店位于郊區，人跡罕至，除了本蒟蒻沒有人來買（6），經過我大腦飛快運轉后，我想到了可以這樣：每天都去挑選最貴的，這樣到最后錢耗得就是最少的啦！

這個例子有點抽象，但能看懂就行（doge），其中我這個“天才策略”就是貪心策略啦，我們可以來驗算一下：當商店有3件物品，價格分別為100 200 300，當我們用其他的方法來買的時候（以200 -100-300為例）,我們可以得出這種方法需要200*1+100*2+300*3=1300元，但當我們用我這種天才方法（300-200-100）時會發現只需要300*1+200*2+100*3=1000元！整整少了300元，夠吃頓火鍋了。

我們轉化到編程中，大概就是這樣：（n為物品數量，ai為每個物品的價值（ai <= 1000），商店物品數量不超過10^5個）

#include <bits/stdc++.h>
using namespace std;int n,a[100005];
long long ans;                   //這個問題是我自己臨時想的，也不知道，開個ll保險點bool cmp(int x,int y){return x > y;                //比較函數（bool型哈），即sort排序的方法，結構體排序就要用到，這里的x>y是指大的排前面，小的往后，即從大到小排列
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}sort(a+1,a+n+1,cmp);         //這里本蒟蒻輸入是1~n，所以根據sort不包頭不包尾性質（自創），要在前后各+1for(int i = 1;i <= n;i++){ans += a[i]*i;           //i為第幾天，這時a數組已排好序，即第i天買第a[i]個物品}cout << ans;                 //輸出
}

so，大概都理解了吧~

接下來我們來說一下這個貪心算法的關鍵：貪心策略的選擇。你想想，有些貪心問題吧，它會有many的方法，我們要在其中選擇出正確的方法，這種方法有一個極其重要的性質——無后效性。聽起來很高大上對不對？其實吧，就是后面的結果不會影響到前面的結果（以上面那個例子來說，就是我第2天買完東西后商店老板不會再說：“我把第1天的價格提高兩倍了，你得給我補回來。”畢竟這樣就成黑商了）。

3.演練

既然大概懂了，那么，來點料吧呵呵...（邪笑）

1.排隊接水

這題目也可以說是老得沒邊了，貪心經典問題（放在某卡牌里幾乎是絕版級的了）：

題目描述

有 n個人在一個水龍頭前排隊接水，假如每個人接水的時間為 Ti，請編程找出這 n個人排隊的一種順序，使得 n個人的平均等待時間最小。

輸入描述

第一行為一個整數 n。

第二行 n個整數，第 i個整數 Ti表示第 i個人的接水時間 Ti?。

輸出描述

輸出文件有兩行，第一行為一種平均時間最短的排隊順序；第二行為這種排列方案下的平均等待時間（輸出結果精確到小數點后兩位）。

樣例1

輸入

10 
56 12 1 99 1000 234 33 55 99 812

輸出

3 2 7 8 1 4 9 6 10 5
291.90

提示

1≤n≤1000，1≤ti≤10^6，不保證 ti 不重復。

我們直接來看題。

這道題其實很簡單，有十個人去接水，每個人接水都要一定時間（也許容積不同吧，全家桶和馬桶不是一個概念），每個人接水時，在后面排隊的是需要等待的，也就是說呢，一個人就會浪費后面x個人的時間，也就是說他會浪費ti*x的時間！太可惡了！

開個玩笑。

這道題我們其實可以發現，當后面排隊的人越多，他所耗的平均時間就會越長，也就是說，這個人接水的時間越長，平均時間也就越長。

可能這種解釋比較模糊，我們以樣例來解釋一下：

我們樣例的輸入中，可以發現1是最短的，1000是最長的。我們以這兩個為開始，假設讓時長為1的人去接，那么10個人的總等待時長就是9*1=9，其次再讓1000來的話，那么這兩人耗費所有人的總時長就是1*9+1000*8=8009，而如果我們反過來，讓1000的那個先接，1后接，則耗費的總時長就是1000*9+1*8=9008 > 8009，這樣我們就可以發現，我們把小的放在前面，大的放在后面（也就是從小到大排）就可以得出最少的總時長和平均時長。

或者這樣解釋，我們假設這10個人已經排好隊，則我們所要的時長之和就是9*a[1]+8*a[2]+7*a[3]+6*a[4]+...+1*a[9]+0*a[10]，這時我們發現，當我們把a[1],a[2]..a[10]從小到大排列后可以得出最終結果是最小的。

因此，我們可以編出以下代碼：

#include <bits/stdc++.h>
using namespace std;int n;
struct node{int num,time;                //這里定義結構體是為了方便把每個人的編號給記錄一下
}t[100005];
double ans;                      //平均時長保留兩位小數，用浮點型bool cmp(node x,node y){return x.time < y.time;      //這里的x.time<y.time就是指按每個元素的time大小從小到大排
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> t[i].time;        //輸入每個人所需的時間t[i].num = i;            //輸入順序即每個人的編號}sort(t+1,t+n+1,cmp);         //排序，cmp上面解釋了for(int i = 1;i <= n;i++){ cout << t[i].num << " "; //這里先輸出最優排序中每個人的順序（即編號，結構體排序中所有元素會隨著所排序的元素一起移動）}for(int i = 1;i <= n;i++){ans += 1.0*t[i].time*(n-i);     //1.0*是為了把這個平均時間轉化為浮點型，后面(n-i)只后面等待的人數} cout << endl;                           //換行別忘了！！！cout << fixed << setprecision(2) << 1.0*ans/n;  //1.0還是轉換（畢竟后面有整除n），前面的fixed和setprecision(2)這種就是保留兩位小數的意思，有點復雜，可以用printf()，見下
//  printf("%.2f",1.0*ans/n);  return 0;                   //好習慣是需要養成的（雖然上面那個例子沒寫，但不要學我不寫哈）  
}

十分抽象，不說什么了，繼續。

2.選修課

題目描述

【題目描述】

周末有n門選修課, 小猴要在n門選修課中選擇盡可能多的課程

已知每門課程的開始時間和結束時間, 不能選時間段上有重復的課程.

---

【輸入格式】

第一行是一個整數n(1≤n≤1000)

接下來n行，每行是2個整數ai,bi(0≤ai<bi≤10^9)，表示每門課程開始、結束的時間。

【輸出格式】

一個整數, 小猴能選的最大課程數量

---

【輸入樣例#1】

3
0 2
2 4
1 3

【輸出樣例#1】

2

這道題其實吧，也不難，總歸要排序。

但它有一個起始時間和終止時間，到底排哪個是個問題。

其實吧，你仔細想想，這道題如果你想要去做的話，那一定要讓這個時間盡量連接在一起，每一段時間都不浪費。

既然這樣，那我們發現結束時間越早，那可選的課程就應該更多，即用結束時間排序更為合理。

同時我們再來想一下貪心策略，結束時間雖然早，但是我們還是要判斷結束時間第二早的那門課程的開始時間是否合理，如果合理就選，不合理就繼續選擇第三早的。

我們用樣例解釋一下：

給出三門課，按結束時間排序后變成了a[1] = 0 2,a[2] = 1 3,a[3] = 2 4。首先我們肯定要選第一個a[1]，然后這時的結束時間便是2，接下來如果我們要選a[2]的話，會發現開始時間<2，時間有重復，不能選；我們再看a[3]，它的開始時間是2，剛好等于a[1]的結束時間，可以選。從而我們選a[1]、a[3]兩節課是最佳選擇。

由此，我們編出以下代碼：

#include <bits/stdc++.h> 
//這里給大家講一下，在cmath庫中有y1是被定義的函數，都是用萬能頭后這個y1就不能作為變量了，所以當你要用y1這個名稱的時候就老老實實將一個個庫寫下來，別用萬能（會報錯）
using namespace std;int n,l,ans;                          //l是選定某節課后最早可以開始上課的時間
struct node{int a,b;                          //a為開始時間，b為結束時間
}c[1005];bool cmp(node x,node y){              //比較函數return x.b < y.b;                
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> c[i].a >> c[i].b;     }sort(c+1,c+n+1,cmp);             //以結束時間排序for(int i = 1;i <= n;i++){if(c[i].a >= l){             //如果這門課程開始時間比上一節課的結束時間晚就選中ans++;                   //統計課程數量l = c[i].b;              //更新最晚時間}}cout << ans;return 0;
}

也是很簡單。

3.Best Cow Line

題目描述

FJ帶著他的N頭奶牛去參加年度最佳農場評選.

評選的組織者會將來自同一個農場的奶牛按照列隊的順序進行登記, 并且只登記每只奶牛名字的首字母. 如果FJ讓Bessie, Sylvia, 和 Dora按這個順序排好隊,FJ的農場就會被登記為字符串"BSD". 登記后所得到的的字符串的字典序最小的農場將會被評為年度最佳農場.(字典序是指從前到后比較兩個字符串大小的方法，首先比較第一個字符，如果不同則第1個字符較小的字符串更小，如果相同，繼續比較第2個字符...如此繼續，來比較整個字符串的大小)

FJ已經將奶牛排好隊, 現在他要進行以下兩種操作共N次, 將奶牛排一個新隊:

1.將原隊伍排第一的奶牛加入新隊伍的末尾

2.將原隊伍排最后的奶牛加入新隊伍的末尾

FJ想要通過以上兩種操作, 構造字典序盡可能小的新隊伍. 輸入原隊伍的順序，輸出字典序最小的新隊伍.

輸入描述

第一行一個正整數N, 表示奶牛的數量(N≤2000)

接下來N行，每行一個大寫英文字母, 代表原隊伍每只奶牛的名字首字母.

輸出描述

輸出字典序最小的新隊伍, 每輸出80個字符就換行.

樣例1

輸入

6
A
C
D
B
C
B

輸出

ABCBCD

這道題也難不倒哪里去，我們稍微看看就會發現其實就兩個判斷：如果隊首跟隊尾的字母不一樣，那么就返回字典序小的那個，否則就繼續往后比。

沒了，就這么簡單。

直接上代碼：

#include<bits/stdc++.h>
using namespace std;int n;
string ans;                      //新隊列
char s[2005];                    //記錄原隊列bool check(int l,int r){         //比較隊首和隊尾的函數if(s[l] != s[r])                  return s[l] < s[r];      //不一樣就返回，這里如果s[l]比s[r]小就會返回true，反之亦然else if(s[l] == s[r])return check(++l,--r);   //否則繼續往后比return true;                 //比到最后都是相等就直接隨便返回其中任意一個
}int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> s[i];}int l = 1,r = n;             //這里類似二分算法，l相當于隊首，r相當于隊尾for(int i = 1;i <= n;i++){if(check(l,r)){ans += s[l];         //如果隊首小，ans字符串就插入隊首l++;                 //隊首已經出列了，現在的隊首就是后一個}else{                   //反之亦然ans += s[r];r--;}if(i%80 == 0){           //滿80進一ans += '\n';         //添加換行符}}cout << ans;                 //輸出最后的字符串return 0;
}

真的不是很難。

4.[NOIP 2002 提高組]?均分紙牌

這道題我也不想多說什么了，二十三年的老題，和劉禹錫“二十三年棄置身”的時間一樣了。

題目描述

有 N 堆紙牌，編號分別為 1,2,…,N。每堆上有若干張，但紙牌總數必為 N 的倍數。可以在任一堆上取若干張紙牌，然后移動。

移牌規則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N?1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣多。

例如 N=4 時，4 堆紙牌數分別為 9,8,17,6。

移動 3 次可達到目的：

• 從第三堆取 4 張牌放到第四堆，此時每堆紙牌數分別為 9,8,13,10。
• 從第三堆取 3 張牌放到第二堆，此時每堆紙牌數分別為 9,11,10,10。
• 從第二堆取 1 張牌放到第一堆，此時每堆紙牌數分別為 10,10,10,10。

輸入格式

第一行共一個整數 N，表示紙牌堆數。
第二行共 N 個整數 A1?,A2?,…,AN?，表示每堆紙牌初始時的紙牌數。

輸出格式

共一行，即所有堆均達到相等時的最少移動次數。

輸入輸出樣例

輸入 #1

4
9 8 17 6

輸出 #1

3

說明/提示

對于 100% 的數據，1≤N≤100，1≤Ai?≤10000。

這題目其實也很簡單，首先，因為他沒說無法均等的情況，所以默認這些卡牌數字之和是能被n整除的，即均等時每張牌的數值。

接下來就是那這個平均數值來比較移動次數了，我們仔細看一下，其實任何一種情況都最多只需要n-1次即可均分（1給/拿2，2給/拿3...n-1給/拿n，最后肯定能保證n為平均值），因此，我們只需要定義一個變量來存儲變換次數，而當這堆紙牌剛好卡在平均數上，那么就可以跳過了，具體操作如下：

for(int i = 1;i <= n-1;i++){         //第n堆能保證為平均數if(a[i]-sum == 0) continue;      //當這堆牌剛好在平均數上時就跳過，同時計數變量不變a[i+1] = a[i]-sum+a[i+1];        //否則就將下一堆的牌給它調到平均數（用后一堆即為無后效性，不會影響前面已擺好的牌）ans++;                           //計數變量，增加移動次數
}

那么再加上其他的輸入輸出，即可得出最終代碼：

#include <bits/stdc++.h>
using namespace std;int n,sum,ans;
int a[105];int main(){cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];sum += a[i];}sum /= n;for(int i = 1;i <= n-1;i++){if(a[i]-sum == 0) continue;a[i+1] = a[i]-sum+a[i+1];ans++;}cout << ans;return 0;
}

撒花??ヽ(°▽°)ノ?

4.習題

也是又到了難為大佬檢查學習成果的時候了，來叭hh（邪笑）

1.導彈攔截

題目描述

某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數據是 <= 50000的正整數），計算要攔截所有導彈，最少要配備多少套這種導彈攔截系統。

輸入描述

第1行一個正整數n （n≤1000）

第2行n個正整數, 不超過50000, 以空格分隔

輸出描述

1行，表示如果要攔截所有導彈，最少要配備多少套這種導彈攔截系統。

樣例1

輸入

8
389 207 155 300 299 170 158 65

輸出

2

2.智力大沖浪

題目描述

小偉報名參加中央電視臺的智力大沖浪節目。本次挑戰賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者m元。先不要太高興！因為這些錢還不一定都是你的？！接下來主持人宣布了比賽規則：

首先，比賽時間分為n個時段，它又給出了很多小游戲，每個小游戲都必須在規定期限ti前完成(1≤ti≤n)。如果一個游戲沒能在規定期限前完成，則要從獎勵費m元中扣去一部分錢wi?，wi為自然數，不同的游戲扣去的錢是不一樣的。當然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內完成，而且都必須從整時段開始。 主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當然更想贏取最多的錢！注意：比賽絕對不會讓參賽者賠錢！

---

【輸入格式】

輸入共四行。

第一行為m，表示一開始獎勵給每位參賽者的錢；

第二行為n，表示有n個小游戲；

第三行有n個數，分別表示游戲1到n的規定完成期限；

第四行有n個數，分別表示游戲1到n不能在規定期限前完成的扣款數。

【輸出格式】

輸出僅一行，表示小偉能贏取最多的錢。

---

【輸入樣例#1】

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

【輸出樣例#1】

9950

---

【數據說明】

對于100%的數據，有n≤500，1≤ti≤n。

3.紅蘋果和綠蘋果

【題目描述】

你想要吃X個紅蘋果和Y個綠蘋果。

目前有A個紅蘋果，美味度分別是p1,p2,??,pA?；B個綠蘋果，美味度分別是q1,q2,??,qB；CC個無色蘋果，美味度分別是r1,r2,??,rC?。

無色蘋果可以染色成紅蘋果或者綠蘋果。選擇若干個（可以是0個）無色蘋果，染成合適的顏色，使得你可以吃到X個紅蘋果和Y個綠蘋果，并且使得吃到的蘋果的美味度總和最大。輸出最大的總和。

---

【輸入格式】

第1行，5個整數X,Y,A,B,C

第2行，A個整數p1,p2,??,pA

第3行，B個整數q1,q2,??,qB

第4行，C個整數r1,r2,??,rC

【輸出格式】

可以吃到的最大的美味度總和

---

【輸入樣例#1】

1 2 2 2 1
2 4
5 1
3

【輸出樣例#1】

12

【樣例#1說明】

吃第2個紅蘋果，第1個綠蘋果，將第1個無色蘋果染成綠蘋果吃掉。美味度總和為12。

---

【輸入樣例#2】

2 2 2 2 2
8 6
9 1
2 1

【輸出樣例#2】

25

---

【輸入樣例#3】

2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

【輸出樣例#3】

74

---

【數據說明】

1≤X≤A≤10^5

1≤Y≤B≤10^5

1≤C≤10^5

1≤pi,qi,ri≤10^9

4.數列分段 Section I

題目描述

對于給定的一個長度為 N的正整數數列 Ai?，現要將其分成連續的若干段，并且每段和不超過 M（可以等于M），問最少能將其分成多少段使得滿足要求。

輸入描述

第1行包含兩個正整數 N,M，表示了數列 Ai的長度與每段和的最大值，第 2行包含 N個空格隔開的非負整數 Ai，如題目所述。

輸出描述

一個正整數，輸出最少劃分的段數。

樣例1

輸入

5 6
4 2 4 5 1

輸出

3

提示

對于20%的數據，有N≤10

對于40%的數據，有N≤1000；

對于100%的數據，有N≤100000,M≤10^9，M大于所有數的最大值，Ai?之和不超過10^9。

將數列如下劃分：

[4][24][51]

第1段和為4，第2段和為6，第3段和為6均滿足和不超過M=6，并可以證明3是最少劃分的段數。

5.小結

其實也沒啥可總結的，反正貪心這種算法也是用處極廣的一種算法，只要能掌握策略的選取（無后效性）基本就可以解決了，沒什么特別難的東西。接下來我們將進入一個極其重要的算法——動態規劃，我將會用5篇左右來具體闡述動態規劃的各種變形，這都是后話了，886~~~~

上一章：廣度優先搜索算法2? ? ? ? ? ? ? ? ? ? ? ? ? 下一章：動態規劃1（序列型動規+最長上升子序列）（未完工）