11292

Question

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2267

Evolution

1. Asc sort head & knight separately by head's diameter & knight's height.
2. For ith head h[i], if there exist a knight whose height k[j] >= h[i], and j (this knight's index) greater than the index of knight who can cut i-1th head(if exists), the jth knight must be the cheapest and most suitable knight to cut ith head, if there doesnt, Loowater is doomed!

Attention

1. UVA use %lld to print long long.
2. c++'s sort automatically sort by asc.

Code

#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    const int MAXN = 2e4 + 4;
    int k[MAXN],h[MAXN];
    int n,m;
    while(scanf("%d%d",&n,&m)==2 && (n||m)){
        for(int i = 0;i < n;i++){
            scanf("%d",h + i);
        }
        for(int i = 0;i < m;i++){
            scanf("%d",k + i);
        }

        sort(h,h + n);
        sort(k,k + m);

        int j = 0;
        long long ans = 0;
        for(int i = 0;i < n;i++){
            for(;j < m && h[i] > k[j];j++){}
            if(j >= m){j++;break;}
            ans += k[j];
            j++;
        }
        if(j > m)printf("Loowater is doomed!
");
        else printf("%lld
",ans);
    }
    return 0;
}