广联达笔试第三题题解
题意：
给定x轴上有n个怪物，每个怪物有对应位置和血量，你拥有一个Aoe技能能使[x-y,x+y]范围内的怪物掉血，x为你使用技能的位置，y为技能范围求最少使用技能次数。
思路：
贪心
先对怪物从小到大排序，每次从消灭最左的怪物，在[最左怪物的位置，最左怪物位置 + 2 * y]区间的怪物也一起掉血。
然后再找下一个血量大于0的怪物，直到消灭所有怪物。
原理：你肯定需要消灭最左的怪物->消灭最左怪物的点肯定在[最左怪物位置，最左怪物位置+y]之间 -> 所以选择[最左怪物的位置，最左怪物位置 + 2 * y]区间的怪物也一起掉血 ->消灭所有怪物
import java.util.Arrays;
import java.util.Scanner;
public class Main3 {
/**
* AOE 打怪
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int y = sc.nextInt();
long[][] monster = new long[n][2];
for (int i = 0; i < n; i++) {
monster[i][0] = sc.nextLong();
monster[i][1] = sc.nextLong();
}
Arrays.sort(monster, (m1, m2) -> (int)(m1[0] - m2[0])); //从小到大排序
long cnt = 0;
int mon = 0;
while (mon < n) {
cnt+= monster[mon][1]; //每次添加的次数为最左怪物的血量
long kill = monster[mon][1];
for (int i = mon; i < n; i++) {
if (monster[i][0] <= monster[mon][0] + 2 * y) { //在[最左怪物+2y]范围内的怪物都掉血
if (monster[i][1] > 0) {
monster[i][1] -= kill;
}
} else {
break;
}
}
while (mon < n && monster[mon][1] <= 0) { //找到下一个有血的怪物
mon++;
}
}
System.out.println(cnt);
}
}
#广联达2021届秋招提前批#
投递美团等公司10个岗位 >
