勇士砍龙头问题

问题描述：你的王国里有一条n个头的恶龙，可以雇佣骑士把它杀死，村里有m个骑士，能力值为x的骑士可以砍掉一个恶龙直径不超过x的头，且需支付金币x，怎样才能杀死恶龙并且支付金币最少？(一个骑士只能砍一个头，雇佣一次）【格式输入】每组数据的第一行为 n,m。下面n行每行为一个整数，代表恶龙头的直径，以下m行每行为一个整数，代表每个骑士的能力，输入结束标志是n=m=0。【样例输入】 2 3 5 4 7 8 4 2 1 5 5 10 0 0 【样例输出】 11 Loowater is doomed!

问题解答：将骑士按能力从大到小排序，头的直径也按从大到小排序，一个一个的砍。

#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn = 20000;

int main(){
    FILE*fp;
    //一个数组用来装头的直径，一个数组用来装骑士的能力
    int A[maxn],B[maxn],n,m,i,cur ,cost ;

    if(NULL==(fp=fopen("a.txt","r")))
    {
        puts("error!");
        return -1;
    }
    while(fscanf(fp,"%d%d",&n,&m) == 2 &&n &&m){
        cost = 0;     //这边切记要置为0，因为每次循环都是一组新的数据
        cur = 0;
        for(i = 0;i < n;i++) fscanf(fp,"%d",&A[i]);
        for(i = 0;i < m ;i++) fscanf(fp,"%d",&B[i]);

        sort(A,A+n);
        sort(B,B+m);

        for(i = 0;i < m;i++){
            if(B[i]>=A[cur]){
                cost += B[i];
                if(++cur == n) break;  //如果所有的头都砍完了就退出循环
            }
        }
        //如果还有头没砍完，则证明无解。
        if(cur < n) printf("Loowater is doomed!\n");
        else printf("%d\n",cost);

    }
    return 0;
}