经典笔试算法题之打小怪兽

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author liusandao
 * @description 
 *              有N只怪兽,每只怪兽有血量a[i],你有M支箭,每支箭可以造成b[i]点伤害,
 *              会消耗c[i]点能量。你要用箭杀死某只怪兽,该箭的伤害必须大于等于怪兽的
 *              血量,打一只怪兽只能用一支箭,每支箭也只能用一次。求,杀死所有怪兽的
 *              最小能量。如果无法杀死所有怪兽,则输出“NO”
 *
 *              第一行T,表示有T组样例
 *              每组样例第一行N,M
 *              每组样例第二行N个数,表示N个怪兽的血量
 *              每组样例第三行M个数,表示每支箭的伤害
 *              每组样例第四行M个数,表示每支箭的消耗
 *
 *              例子
 *              1
 *              3 3
 *              1 2 3
 *              2 3 4
 *              1 2 3
 *
 *              输出:6
 *
 *
 *
 * @date 2020-4-1 18:20
 */
public class Main {
    public static class Arrow{
        public int damage = 0;
        public int cost = 0;
        public Arrow() {
        }
        public Arrow(int damage, int cost) {
            this.damage = damage;
            this.cost = cost;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            int N,M;
            N = sc.nextInt();
            M = sc.nextInt();
            int[] a = new int[N];
            Arrow[] arrows = new Arrow[M];
            for (int i = 0; i < M; i++) {
                arrows[i] = new Arrow();
            }
            for (int i = 0; i < N; i++) {
                a[i] = sc.nextInt();   //HP
            }
            for (int i = 0; i < M; i++) {
                arrows[i].damage = sc.nextInt();  //damage
            }
            for (int i = 0; i < M; i++) {
                arrows[i].cost = sc.nextInt();  //cost
            }
            /*
            血量从高到低杀,每次取伤害高于血量的箭矢中,耗费最低的
             */
            PriorityQueue<Arrow> p = new PriorityQueue<>(new Comparator<Arrow>() {
                @Override
                public int compare(Arrow o1, Arrow o2) {
                    return o1.cost - o2.cost;
                }
            });
            if (M < N){
                System.out.println("No");
            }
            else {
                int ans = 0;
                boolean can = true;
                Arrays.sort(a);
                Arrays.sort(arrows, new Comparator<Arrow>() {
                    @Override
                    public int compare(Arrow o1, Arrow o2) {
                        return o1.damage - o2.damage;
                    }
                });
                int j = M - 1;
                for (int i = N - 1; i >= 0; i--) {
                    while(j >= 0 && arrows[j].damage >= a[i]){
                        p.offer(arrows[j]);
                        j--;
                    }
                    //把伤害超过的弓箭加进去
                    if (p.size() == 0){
                        System.out.println("No");
                        can = false;
                        break;
                    }
                    else {
                        Arrow ar = p.poll();
                        ans += ar.cost;
                    }
                }
                if (can){
                    System.out.println(ans);
                }
            }
        }
    }
}

很多人看到的第一反应是动态规划,感觉和背包问题很像,但是这题其实有更简便的方法,就是贪心。

将怪物按血量从高到低排序,把箭支按伤害从高到低排序,从血量最高的怪物开始遍历,每次把超过当前怪物血量的箭支加入到我们维护的一个最小堆中(代码中我写的堆是Arrow的堆,其实好像可以直接用Integer堆存耗费),堆中的Arrow对象,按照箭支消耗排序。这样,我们每次只需取出当前可用箭支中,消耗最小的那一根即可,这里利用了贪心的思想,不去考虑该箭支用做杀后面的怪物是否更优,因为箭支对于每支怪物消耗的体力一样,而怪物血量从高到底排序,则遍历到后面,箭支数量一定是更多的(因为约束缩小)。这样的话,代码的时间复杂度就是排序的复杂度加上核心遍历的复杂度O(max(nlogn,mlogn)),又因为M一定大于N,因为箭支数量小于N则直接输出No。所以时间复杂度位O(mlogn)。

我个人感觉这题其实还是比较简单的。但是似乎很多人钻进了动态规划的死胡同里,出不来了。这题能否用动态规划求解我不敢妄下定论,但我思考的时候发现这题要用动态规划求解,其状态转移方程十分麻烦。我们都知道0-1背包问题状态转换方程,是不需要考虑之前状态装了哪些物品的,我们只需要知道背包剩余容量,以及装入当前该物品,是否比不装入好(跟两个值比较)。但是这题不仅要记录状态,还要记录在当前最优状态下,已使用过哪些箭矢(因为箭矢不能重复使用),这是此题与0-1背包问题不同的地方。

如果有想到用动态规划解题的好思路,可以评论,我只是个算法小菜鸡。欢迎指教。

package exam.written.alibaba;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
* @author liusandao
* @description Alibaba42
* 有N只怪兽,每只怪兽有血量a[i],你有M支箭,每支箭可以造成b[i]点伤害,
* 会消耗c[i]点能量。你要用箭杀死某只怪兽,该箭的伤害必须大于等于怪兽的
* 血量,打一只怪兽只能用一支箭,每支箭也只能用一次。求,杀死所有怪兽的
* 最小能量。如果无法杀死所有怪兽,则输出“NO”
*
* 第一行T,表示有T组样例
* 每组样例第一行N,M
* 每组样例第二行N个数,表示N个怪兽的血量
* 每组样例第三行M个数,表示每支箭的伤害
* 每组样例第四行M个数,表示每支箭的消耗
*
* 例子
* 1
* 3 3
* 1 2 3
* 2 3 4
* 1 2 3
*
* 输出:6
*
*
*
* @date 2020-4-1 18:20
*/

public class Alibaba42 {

public static class Arrow{
public int damage = 0;
public int cost = 0;

public Arrow() {
}

public Arrow(int damage, int cost) {
this.damage = damage;
this.cost = cost;
}

}

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int t = 0; t < T; t++) {

int N,M;
N = sc.nextInt();
M = sc.nextInt();

int[] a = new int[N];
Arrow[] arrows = new Arrow[M];
for (int i = 0; i < M; i++) {
arrows[i] = new Arrow();
}

for (int i = 0; i < N; i++) {
a[i] = sc.nextInt(); //HP
}
for (int i = 0; i < M; i++) {
arrows[i].damage = sc.nextInt(); //damage
}
for (int i = 0; i < M; i++) {
arrows[i].cost = sc.nextInt(); //cost
}

/*
血量从高到低杀,每次取伤害高于血量的箭矢中,耗费最低的
*/

PriorityQueue<Arrow> p = new PriorityQueue<>(new Comparator<Arrow>() {
@Override
public int compare(Arrow o1, Arrow o2) {
return o1.cost - o2.cost;
}
});

if (M < N){
System.out.println("No");
}
else {
int ans = 0;
boolean can = true;
Arrays.sort(a);
Arrays.sort(arrows, new Comparator<Arrow>() {
@Override
public int compare(Arrow o1, Arrow o2) {
return o1.damage - o2.damage;
}
});
int j = M - 1;
for (int i = N - 1; i >= 0; i--) {
while(j >= 0 && arrows[j].damage >= a[i]){
p.offer(arrows[j]);
j--;
}
//把伤害超过的弓箭加进去
if (p.size() == 0){
System.out.println("No");
can = false;
break;
}
else {
Arrow ar = p.poll();
ans += ar.cost;
}
}
if (can){
System.out.println(ans);
}
}
}

}

}


上一篇:Python 中的时间处理包datetime和arrow


下一篇:STL容器之string字串