挑戰程式設計競賽筆記-貪心算法

2.2 貪心算法

貪心算法的精髓在于，遵循某種規則，不斷地選取目前最優解。

硬币問題
假設有 1 元，5元，10元，50元，100元，500元的硬币C1，C5，C10，C50，C500枚，現在需要湊出 A 元
問如何組合才能使硬币的數量最少？
           

這道題給人的印象就是，為了使得硬币數目最少，盡可能使用面值大的硬币。這種政策就是計算過程中的規則。盡可能使用最大面值，就是目前最優解。

是以，使用每個硬币的數目為：

int t = min(A/Y ，Y_Max);	//A為目标，Y為面值，Y_Max為面值為Y的硬币數目。
           

下面練習一道POJ3617：

2.2.1.BestCowLine

給定長度為N的字元串S,要構造一個長度為N的字元串T,最開始T是一個空串，随後反複進行如下操作：
		1.從S的頭部删除一個字元，加到T的尾部
		2.從S的尾部删除一個字元，加到T的頭部
	目标是建構一個字典序盡可能小的字元串T。
           

這道題的貪心政策就是，每次都選取字元串S兩頭字典序較小的那個。因為規定隻能從兩端取，是以若兩端的字典序有差别，則可以直接根據目前情況選擇目前最優解。我們的需求也是，每次要選擇小字典序的字母插入隊列。

但是，如果字典序一樣該選哪個呢？對于相同的字典序，對于目前情況是沒有差別的。可是，如果一個字典序是ZB…CZ，那麼如果選擇右側的先，則會導緻接下來選擇的是ZC…而先選左邊，則會産生ZB，這樣明顯選左邊産生的字典序更小。是以，對于相同的兩端，我們應該持續比較下一個字元。如果下一個字元也是相同的，則要循環下去。

我其實還思考了蠻久了，為什麼要一直循環下去。後來總結道：

|									|
|	|				    		|	|
|	|	|		   	 		|  	|	|	
|	|	|	_  .....   |	|	|	|
           

如果以豎線高低作為字典序高低，隻有這種排列的順序，按照上面循環比對才有效。

即 “相等項後面字典序遞減”

如上圖，選取左側的字典序是 4-3-2-0 ，而選右邊則是4-3-2-1，字典序右邊高。（讓我們忽略省略号，隻考慮接下來四個字母）

#include<stdio.h>

int n;//length
char str[2001];
//char ans[2000];

void create(char* str){
    int i = 0;
    int a = n-1;
    int count = 0;
    bool left=false;//預設推右邊
    while(i<=a){
        for(int j=0;i+j<=a-j;j++){//如果字典序相同
            if(str[i+j]<str[a-j]){
                left = true;
                break;
            }
            else if(str[i+j]>str[a-j]){
                left = false;
                break;
            }
        }
        
        if(left){
            putchar(str[i++]);
        }
        else
        {
            putchar(str[a--]);
        }
    }
    putchar('\n');
}

int main(){
    
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf(" %c\n", & str[i]);
        }
        str[n]='\0';
        
        create(str);
        
        
    }
    
    
    
}
           

2.2.2 Saruman’s Army

poj 3069

在一條直線上，有n個點。從這n個點中選擇若幹個，給他們加上标記。
對于每一個點，其距離為R以内的區域裡必須有一個被标記的點。問至少要有多少點被加上标記。
           

這道題的貪心政策是，從左到右看這些點。遇到第一個點，以它為圓心畫一個半徑為R的圓，右側離圓最近的點作為第一個标記點。為什麼不選第一個點作為标記點呢？如果把這個作為薩魯曼（魔戒梗）的施法範圍，第一個人作為标記點，其左側并沒有覆寫任何點。這樣就會造成浪費。

第二次，我們就選取上一次标記點的下一個點，作為半徑圓心，再按照第一次尋找那樣選取點。

直到圓的右側沒有點的時候，程式退出。

這道題感覺還挺簡單的，并沒有去做它。

2.2.3 Fence Repair

poj 3253

有一個農夫要把一個木闆钜成N塊給定長度的小木闆，每一次費用就是目前鋸的這個木闆的長度  給定小木闆的個數n，各個要求的小木闆的長度。求最小費用
如：要5，5，8的木闆，需要先将總長度18鋸成10，8 再鋸成5，5 。最小花費為28.
           

這道題和搬運水果一樣，相當于搬運水果的時空倒流。也就是，我們将兩塊木闆合到一起，花費的代價是這兩塊木闆長度的和。現在要把他們合成一塊，需要最少多少的代價。

我們知道，每次合并能減少一塊，是以一定需要N-1次合并才能合成一塊。但是我們如何選取呢？

根據哈夫曼樹，我們應該盡可能使得代價小的木闆在葉節點。相當于重複将他們多次合并。處于越深的葉節點，相當于合并這塊木闆的次數最多。而使得次數多的代價小，能達到最優解。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int n;
    priority_queue<int,vector<int>,greater<int> > c;
    int s;
    
    while(scanf("%d",&n)!=EOF){
        long long ans=0;
        while(!c.empty())c.pop();
        for(int i=0;i<n;i++){
            scanf("%d",&s);
            c.push(s);
        }
        
    int a,b;
    if(c.size()==1){
        ans = c.top();
        break;
    }
    while(!c.empty()){
        a = c.top();
        c.pop();
        b = c.top();
        c.pop();
        ans += a+b;
        c.push(a+b);    
        if(c.size()==1)break;
    }
    printf("%lld\n",ans);
}
}
           

上面的代碼使用了優先隊列

priority_queue<int >a 
           

這樣定義預設是大頂堆結構，即先出隊列的是大的值。

priority_queue<int ,vector<int>,greater<int> > a
           

定義了一個小頂堆隊列。

這一資料結構在 #queue 頭檔案裡。