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