勇者鬥惡龍(The Dragon of Loowater, UVa 11292)
你的王國裡有一條n個頭的惡龍,你希望雇一些騎士把它殺死(即砍掉所有頭)。村裡有m個騎士可以雇傭,一個能力值為x的騎士可以砍掉惡龍一個直徑不超過x的頭,且需要支付x個金币。如何雇傭騎士才能砍掉惡龍的所有頭,且需要支付的金币最少?注意,一個騎士隻能砍一個頭(且不能被雇傭兩次)。
【輸入格式】
輸入包含多組資料。每組資料的第一行為正整數n和m(1≤n,m≤20 000);以下n行每行為一個整數,即惡龍每個頭的直徑;以下m行每行為一個整數,即每個騎士的能力。輸入結束标志為n=m=0。
【輸出格式】
對于每組資料,輸出最少花費。如果無解,輸出“Loowater isdoomed!”。
【樣例輸入】
2 3
5
4
7
8
4
2 1
5
5
10
0 0
【樣例輸出】
11
Loowater is doomed!
思路:
砍得頭越多的騎士價格越貴,那麼我們就不能浪費,一個c=b[i]-a[i],這個c應該要大于0但是要足夠小,是以我們進行排序依次比對就行了
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MAX 20005
int a[MAX];
int b[MAX];
int main(){
int n ,m ;
while(cin>>n>>m){
if(n == 0 && m == 0)
break;
for( int i = 0 ; i < n ; i++ )
cin>>a[i];
for( int j = 0 ; j < m ; j++ )
cin>>b[j];
sort(a,a+n);
sort(b,b+m);
int cur = 0 ;
int cost = 0 ;
for( int i = 0 ; i < m ; i++ ){
if(b[i] >= a[cur] ){
cost += b[i];
cur++;
if(cur == n)
break;
}
}
if(cur < n)
printf("Loowater is doomed!\n");
else
printf("%d\n",cost);
}
return 0;
}
``