时间限制: 1 Sec 内存限制: 128 MB 提交: 152 解决: 76 您该题的状态：已完成 [提交][状态][讨论版] 题目描述 动物园有一条n个头的恶龙，你希望雇佣一些骑士把它杀死（也就是砍掉所有的头）。现在有m个骑士可以雇佣，一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头，且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头，并且支付最小的金币？（注意：一个骑士只能砍一个头并且仅能被雇佣1次。） 输入 输入多组数据，第一行二个整数n、m，（1<=n,m<=20000）;以下n行每行为一个整数，即恶龙每个头的直径，以下m行为一个整数，即每个骑士的能力。输入结束标志为n=m=0. 输出 对于每组数据，输出最少花费。如果无解，输出：“Loowater is doomed!”
提示：因为要保证用的钱最少，所以先把骑士按照能力值从小到大进行排序。然后从最小的开始一个一个进行匹配。
样例输入 2 3 5 4 7 8 4 2 1 5 5 10 0 0 样例输出 11 Loowater is doomed! AC：
#include<iostream> #include<algorithm> using namespace std; int main(){ int n , m , a[20001] , b[20001]; while ( cin >> n >> m && n!=0 && m!=0) { int sum = 0 , num =0 , cum = 0; for( int i = 0 ;i < n ; i ++){//n头龙 cin >> a[i]; cum += a[i]; } for ( int i = 0 ; i < m ; i ++){//m个骑士 cin >> b[i]; } sort ( a , a+n); sort ( b , b+m); int t = 0; for ( int i = 0 ;i < m ; i ++){ if (b[i] >= a[t] ){ sum += b[i]; if ( ++ t == n){//一旦把龙杀完了就结束循环 break; } } } if ( t < n){ cout<<"Loowater is doomed!\n"; }else{ cout << sum << endl; } } return 0; }