Greedy Algorithm

贪心算法又称贪婪算法，是遵循某种规则，不断贪心地选取当前最优策略的算法。贪心算法的关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。接下来介绍几个贪心算法的典型例子。

Question 1

question1

Analysis

这个问题的最优解法是每次选择结束最早的工作，这样参与的工作最多。

Solution

//
//  greedy1.cpp
//  GREEDY
//
//  Created by dusign on 2019/11/18.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100000;

void solve(int n, int *s, int *t){
    pair<int, int> itv[n];
    
    for(int i = 0; i < n; i++){
        itv[i].first = t[i];
        itv[i].second = s[i];
    }
    
    sort(itv, itv + n);
    
    int ans = 0, sign = 0;
    for(int i = 0; i < n; i++){
        if(sign < itv[i].second){
            ans++;
            sign = itv[i].first;
        }
    }
    
    cout << ans <<endl;
}

int main(){
    int n, s[MAX_SIZE], t[MAX_SIZE];
    
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> s[i];
    for(int i = 0; i < n; i++)
        cin >> t[i];
    
    solve(n, s, t);
}

Question 2

question2

Analysis

这个问题的最优解法是每次取头部和尾部中最小的一个就行，如果头部和尾部相同的话就继续比较头部和尾部的下一位。

Solution

//
//  greedy2.cpp
//  GREEDY
//
//  Created by dusign on 2019/11/18.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>

using namespace std;

const int MAX_SIZE = 2000;

void solve(int N, char *S){
    int a = 0, b = N - 1;
    
    while(a <= b){
        bool left = false;
        
        for(int i = 0; a + i <= b - i; i++){
            if(S[a + i] < S[b - i]){
                left = true;
                break;
            }else if(S[a + i] > S[b - i]){
                left = false;
                break;
            }
        }
        
        if(left) cout << S[a++];
        else cout << S[b--];
    }
    
    cout << endl;
}

int main(){
    int N;
    char S[MAX_SIZE];
    
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> S[i];
    
    solve(N, S);
}

Question 3

question3

Analysis

这个问题的最优解法是从第一个开始，把所有的点分成若干组，每一组两端的距离小于等于 2R，每一组中间的一个点添加标记，这样添加标记的点就是最少的。

Solution

//
//  greedy3.cpp
//  GREEDY
//
//  Created by dusign on 2019/11/25.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>

using namespace std;

const int MAX_SIZE = 1000;

void solve(int N, int R, int *X){
    sort(X, X + N);
    int i = 0, ans = 0;
    while(i < N){
        int s = X[i];
        
        while(i < N && X[i] <= s + R) i++;
        
        int p = X[i - 1];
        
        while(i < N && X[i] <= p + R) i++;
        
        ans++;
    }
    cout << ans;
}

int main(){
    int N, R, X[MAX_SIZE];
    
    cin >> N >> R;
    for(int i = 0; i < N; i++)
        cin >> X[i];
    
    solve(N, R, X);
}

Question 4

question3

Analysis

这个问题的最优解法是木板在切割的过程中越长的木板越早割，短的木板留到最后切割，这样的话开销最少。整个切割过程也可以看成一个二叉树，每一层都会有开销，这样的话长的木板在上面开销才最少。

Solution

//
//  greedy4.cpp
//  GREEDY
//
//  Created by dusign on 2019/11/27.
//  Copyright © 2019 gang du. All rights reserved.
//

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 50000;

void solve(int N, int *L){
    long long ans = 0;

    while(N > 1){
        int mii1 = 0, mii2 = 1;
        if(L[mii1] > L[mii2]) swap(mii1, mii2);

        for(int i = 2; i < N; i++){
            if(L[i] < L[mii1]){
                mii2 = mii1;
                mii1 = i;
            }else if(L[i] < L[mii2]){
                mii2 = i;
            }
        }

        int t = L[mii1] + L[mii2];
        ans += t;

        if(mii1 == N-1) swap(mii1, mii2);
        
        L[mii1] = t;
        L[mii2] = L[N - 1];

        N--;
    }

    cout << ans;
}

int main(){
    int N, L[MAX_SIZE];
    
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> L[i];
    
    solve(N, L);
}

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

00:00