【題目敘述】https://vjudge.net/problem/UVA-11292
【解題想法】Greedy
- 國王打算派騎士去殺一隻多頭龍(每個頭的大小都不同)，每一位騎士負責砍一個頭。只有當騎士的身高大於龍頭的直徑時，才能順利砍下。
- 每一位順利砍下龍頭的騎士，將得到與其身高等值的金幣。
- 國王希望付出的金幣越少越好？
- 問：能否順利砍掉全部的頭？可以的話，國王需付出多少金幣？
#include <bits/stdc++.h>
using namespace std;
long long n, k, a, ans;
vector <int> d, v;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> n >> k){
if (n == 0 && k == 0) break;
d.clear();
for (int i = 0; i < n; i++){
cin >> a;
d.push_back(a);
}
v.clear();
for (int i = 0; i < k; i++){
cin >> a;
v.push_back(a);
}
if (n > k){
cout << "Loowater is doomed!\n";
continue;
}
sort(d.begin(), d.end());
sort(v.begin(), v.end());
int idx = 0;
bool flag = true;
ans = 0;
for (int i = 0; i < n; i++){
while (v[idx] < d[i] && idx < k-1) idx++;
if (v[idx] < d[i]){
flag = false;
break;
}
ans += v[idx];
idx++;
}
if (!flag) cout << "Loowater is doomed!\n";
else cout << ans << "\n";
}
}