三、貪心演算法：

演算法思想：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

經典例題：選最大（野題）

給你N個數，要求你選出K個數使他們的和最大。

思路：我們進行K次貪心，每次我們都「貪」剩下的所有數中最大的，選擇後拿走，這樣就能保證我選的K個數總和最大。做法就是把N個數從大到小排序選擇前K個即可。

經典例題：國王遊戲（Luogu 1080）

恰逢 H 國國慶，國王邀請 n 位大臣來玩一個有獎遊戲。首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數。然後，讓這 n 位大臣排成一排，國王站在隊伍的最前面。排好隊後，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然後向下取整得到的結果。

國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞儘可能的少。注意，國王的位置始終在隊伍的最前面。

思路：此題要用到高精度，考慮最後一個大臣，顯然他很可能是金幣最多的人。我們要讓他的金幣盡量的少。之前的大臣左手的數肯定會乘起來，所以我們要使S/A/B盡量的大。（設S是左手所有數的乘積），即讓A*B盡量的大。選完最後一個後，我們把他踢掉，然後再找一個最後的大臣。如此往複，相當於就是對A*B排序。

基於交換的證明：假設兩個相鄰的大臣i,j，而前面的人總乘積為S。

當i在j前面時，設ans1=max(s/i.b,s*i.a/j.b);

當j在i前面時，設ans2=max(s/j.b,s*j.a/i.b);

所以要使得i在j前面，必須要ans1<ans2，所以：按照ai*bi排序，條件為x.a*x.b<y.a*y.b才是正解！

ZHX給的一個小小的Tip：

當我們做貪心時候不知道按照什麼來排序，這時候就可以慢慢試，按照a×b、a+b、ab…這些條件來排序，看看哪個計算出來的結果最符合標答^_^，真。。。是個有用的Tip啊！

四、搜索演算法：

1.三種不同的搜索問題：

①最優性問題：例如：有N個數，從中選出K個數滿足和最大。

②計數問題：例如：有N個數，從中選出K個數的方案數目有多少。

③方案問題：例如：有N個數，從中選出K個數滿足已知條件，輸出其中M種方案，一般這第三類問題可以在第二類問題中解決。

2.兩種不同的搜索方法：

①BFS（廣度優先搜索）：目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

②DFS（深度優先搜索）：其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

3.搜索優化技巧：

①剪枝：當搜索到一個狀態時候，發現當前狀態不滿足條件，就不繼續往下搜，而不是等到搜索完畢才判斷是否滿足條件。

②BFS—meet in the middle：雙向搜索（前提是要知道最終狀態的樣子）

舉個栗子：我們有一個滿三叉樹，深度為k，我們搜索到最後一層的狀態數為3k-1，這樣要花費的時間非常多。

已知了起始狀態和最終狀態，要用BFS求出起始到最終所經過的那些狀態，其實可以從起始狀態往後走k/2個狀態（k為初末總狀態數），再從最終的N個狀態往前走k/2個狀態，一定會在中間某個節點相遇，這樣聯通起了整個狀態。

時間、空間複雜度從O(X)變為O(sprt(X))。

③重複結構利用（計數問題）：這個我不會~

④卡時（最優化問題）：我們在面對求最優值問題的時候，如果找到一個更優的值，更新一下ans的值，但是如果你還沒搜索完畢，時間已經快要到達上限了，這時候就會爆0，意思就是要在程序運行時間快要到達題目限制時候，把當前我們找到的ans輸出來！這樣你就會從「得0分」變成「至少得0分」！超級有用啊啊！！

#include <stdio.h>

#include <stdlib.h>//exit()要用到的庫函數

#include <time.h>//clock()去官網看能不能用，否則就會變成至多零分了……

int t;//程序開始運行時候當前系統時間

void dfs()

{

/*假如題目限制時間為2000ms*/

if(clock()-t>=1995)//程序運行時間=程序執行到此當前系統時間-程序開始系統時間（以ms為單位）

{

shuchujie();//輸出答案（保守一點可能需要5ms傳入輸出函數並輸出）

exit(0);//直接銷毀程序！

}

else

{

;//繼續往下搜

}

}

int main()

{

t=clock();//記錄一下當前時間

return 0;

}

⑤數據結構優化：一般不會出到那麼難（笑哭臉）

五、奇怪的東西：

越來越有用的東西——讀入優化（可以加快讀入int的速度）：

我們平時從一個文件裡面讀入一百萬個數數據，基本接近一秒了（那還玩個P啊！），讀入優化基本思想就是：把讀入的數據拆成一個字元一個字元的來讀入，因為字元讀入比int快~

下面給出了讀入優化int的代碼，直接調用就可以了噢~當然只限於讀入非負整數，如果是負數、小數、科學計數法的話還要加上一些判斷。

這個什麼原理相信各位看官稍加思考便可看明白。

#include <stdio.h>

int getint()

{

char c= ;

while(c<0||c>9) c=getchar();

int x=0;//x為這個數字的前綴

while(c>=0&&c<=9)

{

x=x*10+c-0;

c=getchar();

}

return x;

}

int main()

{

int a;

a=getint();//調用讀入優化

printf("%d ",a);

return 0;

}

推薦閱讀：