1994 - 捕杀恶龙！

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 128 MB

动物园有一条n个头的恶龙，你希望雇佣一些骑士把它杀死（也就是砍掉所有的头）。现在有m个骑士可以雇佣，一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头，且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头，并且支付最小的金币？（注意：一个骑士只能砍一个头并且仅能被雇佣1次。）

题目输入

输入多组数据，第一行二个整数n、m，（1<=n,m<=20000）;以下n行每行为一个整数，即恶龙每个头的直径，以下m行为一个整数，即每个骑士的能力。输入结束标志为n=m=0.

题目输出

对于每组数据，输出最少花费。如果无解，输出：“Loowater is doomed!”

提示：因为要保证用的钱最少，所以先把骑士按照能力值从小到大进行排序。然后从最小的开始一个一个进行匹配。

输入/输出样例

输入格式

输出格式

11
Loowater is doomed!

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;
}

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;
}

Java解答

import java.util.Scanner;
class Main {
	Node firstNode=new Node(0);
	Node secondNode=new Node(0);
	int sizeA=1;
	int sizeB=1;
	public int getSizeA() {
		return sizeA;
	}
	public int getSizeB() {
		return sizeB;
	}
	public static void main(String[] args) {
		Scanner reader=new Scanner(System.in);
		Main test=new Main();
		boolean flag=true;
		while(flag){
			int n=reader.nextInt();
			int m=reader.nextInt();
			if(n==0&&m==0){
				flag=false;
			}else{
				int[] a=new int[n];
				int[] b=new int[m];
				for(int i=0;i<n;i++){
					a[i]=reader.nextInt();
				}
				for(int i=0;i<m;i++){
					b[i]=reader.nextInt();
				}
				test.sort(a);
				test.sort(b);
				
				test.create1(test.firstNode, a);
				test.create2(test.secondNode, b);
				int c=test.abcd(test.firstNode, test.secondNode);
				if(c==-1){
					System.out.println("Loowater is doomed!");
				}else{
					System.out.println(c);
				}
			}
		}
	}
	public int abcd(Node first,Node second){
		int sum=0;
		if(getSizeA()>getSizeB())return -1;
		while(first.next!=null){
			Node p=first.next;
			Node q=second.next;
			if(p.data<=q.data){
				remove1(1);
				remove2(1);
				sum=sum+q.data;
			}else if(p.data>q.data){
				remove2(1);
			}
			if(second.next==null&&first.next!=null){
				return -1;
			}
		}
		return sum;
		
		
	}
	//获得idx位置的节点
	public Node getNode(int idx,Node node){
		Node p=node;
		for(int i=0;i<idx-1;i++){
			p=p.next;
		}
		return p;
	}
	// 删除单链表中的元素
	public void remove1(int idx){
		Node p=firstNode;
		for(int i=0;i<idx-1;i++){
			p=p.next;
		}
		Node node=p.next.next;
		p.next=node;
		sizeA--;
	}
	public void remove2(int idx){
		Node p=secondNode;
		for(int i=0;i<idx-1;i++){
			p=p.next;
		}
		Node node=p.next.next;
		p.next=node;
		sizeB--;
	}
	// 对数组进行构造单链表
	public void create1(Node node, int[] a) {
		Node p = node;
		for (int i = 0; i < a.length; i++) {
			p.next = new Node(a[i]);
			p = p.next;
			sizeA++;
		}
	}
	public void create2(Node node, int[] a) {
		Node p = node;
		for (int i = 0; i < a.length; i++) {
			p.next = new Node(a[i]);
			p = p.next;
			sizeB++;
		}
	}
	// 对输入的数组进行排序
	public void sort(int[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j < a.length - 1; j++) {
				if (a[j + 1] < a[i]) {
					int c = a[j + 1];
					a[j + 1] = a[i];
					a[i] = c;
				}
			}
		}
	}

	// 节点类
	private static class Node {
		int data;
		Node next;

		Node() {
		}

		Node(int date) {
			this.data = date;
			this.next = null;
		}

		public Node(int d, Node n) {
			this.data = d;
			this.next = n;
		}
	}
}

上一题下一题代码讨论统计