貪心_勇者鬥惡龍

<<算法競賽入門經典-訓練指南>>第一道題目.

被這本書吓到了, 以為都是難題. 這道題不難, 思路是貪心.

時間複雜度也隻有O(n)

第一個版本核心部分雖然是二重循環嵌套, 但私以為有if控制條件, 實際上計算量是O(n)的.

#include <bits/stdc++.h>
using namespace std;

void loop(int n, int m)
{
    int *a = new int [n], *b = new int [m];
    for(int i = ; i < n; ++i) 
        cin >> a[i];
    for(int j = ; j < m; ++j)
        cin >> b[j];
    sort(a, a + n);
    sort(b, b + m);
    int ans = , flag = ;
    bool f = ;
    for(int i = ; i < n; ++i) {
        f = ;
        for(int j = flag; j < m; ++j) {
            if(b[j] >= a[i]) {
                f = ;
                flag = j + ;
                ans += b[j];
                break;
            }
        }
    }
    if(!f) cout << "Loowater is doomed!\n";
    else cout << ans << endl;
}

int main()
{
    int n, m;
    while(cin >> n >> m && n != ) {
        loop(n, m);
    }
}

/*
2 3
5 4 7 8 4
2 1
5 5 10
0 0
*/
           

第二版本是借鑒了書上的, 時間複雜度隻有O(m).

這種思維或是解題方法算是很巧妙了.

兩數組都排下序, 然後從小到大互相比較. 同時根據條件移動.

#include <bits/stdc++.h>
using namespace std;

void loop(int n, int m)
{
    int *a = new int [n], *b = new int [m];
    for(int i = ; i < n; ++i) 
        cin >> a[i];
    for(int j = ; j < m; ++j)
        cin >> b[j];
    sort(a, a + n);
    sort(b, b + m);
    int cnt = , ans = , flag = ;
    for(int i = ; i < m; ++i) {
        if(b[i] >= a[cnt++]) {
            ans += b[i];
            if(cnt == n) {
                flag = ;
                break;
            }
        }   
    }
    if(flag) cout << ans << endl;
    else cout << "Loowater is doomed!\n";
}

int main()
{
    int n, m;
    while(cin >> n >> m && n != ) {
        loop(n, m);
    }
}

/*
2 3
5 4 7 8 4
2 1
5 5 10
0 0
*/