1994 - 捕杀恶龙！
动物园有一条n个头的恶龙，你希望雇佣一些骑士把它杀死（也就是砍掉所有的头）。现在有m个骑士可以雇佣，一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头，且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头，并且支付最小的金币？（注意：一个骑士只能砍一个头并且仅能被雇佣1次。）
Input
输入多组数据，第一行二个整数n、m，（1<=n,m<=20000）;以下n行每行为一个整数，即恶龙每个头的直径，以下m行为一个整数，即每个骑士的能力。输入结束标志为n=m=0.
Output
对于每组数据，输出最少花费。如果无解，输出：“Loowater is doomed!”
提示：因为要保证用的钱最少，所以先把骑士按照能力值从小到大进行排序。然后从最小的开始一个一个进行匹配。
Examples
Input
2 3 5 4 7 8 4 2 1 5 5 10 0 0
Output
11 Loowater is doomed!
Solution C
#include<stdio.h> int a[21000]; struct{int s;int flag;}b[21000]; int main(void) { int i,j,k,n,m,sum=0,t; scanf("%d%d",&n,&m); while(n!=0||m!=0) {sum=0; for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<m;i++) {scanf("%d",&b[i].s); b[i].flag=0;} if(n>m) {printf("Loowater is doomed!\n");scanf("%d%d",&n,&m);continue;} else {for(k=1;k<n;k++) for(j=0;j<n-k;j++) if(a[j]>a[j+1]) { t=a[j];a[j]=a[j+1];a[j+1]=t; } for(k=1;k<m;k++) for(j=0;j<m-k;j++) if(b[j].s>b[j+1].s) { t=b[j].s;b[j].s=b[j+1].s;b[j+1].s=t; } for(i=0;i<n;i++) {for(j=0;j<m;j++) if(b[j].s>=a[i]&&b[j].flag==0) {sum=sum+b[j].s;b[j].flag=1;break;} if(j==m) {printf("Loowater is doomed!\n");break;break;scanf("%d%d",&n,&m);continue;} } printf("%d\n",sum); scanf("%d%d",&n,&m);} } return 0; }
Solution C++
#include <stdio.h> #include <math.h> #include <iostream> #include <cstdarg> #include <algorithm> #include <string.h> #include <stdlib.h> #include <string> #include <list> #include <vector> #include <map> #define LL long long #define M(a) memset(a, 0, sizeof(a)) using namespace std; void Clean(int count, ...) { va_list arg_ptr; va_start (arg_ptr, count); for (int i = 0; i < count; i++) M(va_arg(arg_ptr, int*)); va_end(arg_ptr); } int d[20009], p[20009]; int main() { int n, m, kill, pay; while (~scanf("%d%d", &n, &m) && (n || m)) { Clean(2, d, p); for (int i = 1; i <= n; i++) scanf("%d", &d[i]); for (int i = 1; i <= m; i++) scanf("%d", &p[i]); sort(d + 1, d + n + 1); sort(p + 1, p + m + 1); kill = pay = 0; for (int i = 1, j = 1; i <= n && j <= m; i++) { while (d[i] > p[j]) j++; if (p[j] >= d[i]) kill += 1, pay += p[j++]; } if (kill >= n) printf("%d\n", pay); else puts("Loowater is doomed!"); } return 0; }