【题解】UVa P11292 【Dragon of Loowater】

题意翻译

你的王国里有一条$n$个头的恶龙,你希望雇佣一些骑士把它杀死(即砍掉所有头)。村里有$m$个骑士可以雇佣,一个能力值为$x$的骑士可以砍掉恶龙一个直径不超过$x$的头,且需要支付$x$个金币。如何雇佣骑士才能砍掉龙的所有头,且需要支付的金币最少?注意,一个骑士只能砍一个头。(且不能被雇佣两次)。

题解

把雇佣来的骑士按能力从小到大排序,头的直径从小到大排序,然后一个一个砍就好了。

#include<cstdio>
#include<algorithm>

namespace OI{
    using std::sort;
}
using namespace OI;

const int MAXN = 20000 + 6;
int A[MAXN],B[MAXN];

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m) == 2 && n && m){
        for(int i = 0;i < n;i++){
            scanf("%d",&A[i]);
        }
        for(int i = 0;i < m;i++){
            scanf("%d",&B[i]);
        }
        
        sort(A,A + n);
        sort(B,B + m);
        
        int id = 0,cost = 0;
        for(int i = 0;i < m;i++){
            if(B[i] >= A[id]){
                cost += B[i];
                if(++id == n){
                    break;
                }
            }
        }
        if(id < n){
            printf("Loowater is doomed!\n");
        }else{
            printf("%d\n",cost);
        }
    }
    
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注