题目描述：

在一个2D横版游戏中，所有的怪物都是在X轴上的，每个怪物有两个属性X和HP，分别代表怪物的位置和生命值。

玩家控制的角色有一个AOE（范围攻击）技能，玩家每次释放技能可以选择一个位置x，技能会对[x-y,x+y]范围内的所有怪物造成1点伤害，请问，玩家最少需要使用多少次技能，才能杀死所有怪物，怪物血量清0即视为被杀死。

输入描述

输入第一行包含一个两个正整数n和y，分别表示怪物的数量和技能的范围。（1<=n<=100000）

接下来有n行，每行有两个正整数x和hp分别表示一只怪物的位置和血量。(1<=x,hp<=10^9)

输出描述

输出仅包含一个整数，表示最少使用的技能次数。

样例输入

3 5 1 10 10 5 22 3

样例输出

复盘：贪心

先对怪物从小到大排序，每次从消灭最左的怪物，在[最左怪物的位置，最左怪物位置 + 2 * y]区间的怪物也一起掉血。然后再找下一个血量大于0的怪物，直到消灭所有怪物。

原理：你肯定需要消灭最左的怪物->消灭最左怪物的点肯定在[最左怪物位置，最左怪物位置+y]之间 -> 所以选择[最左怪物的位置，最左怪物位置 + 2 * y]区间的怪物也一起掉血，直到消灭所有怪物

package com.yyc.test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Test {

    public static void main(String[] args) {
        int n = 3, y = 5;
        int[][] nums = new int[3][2];
        nums[0][0] = 1;
        nums[0][1] = 10;
        nums[1][0] = 10;
        nums[1][1] = 5;
        nums[2][0] = 22;
        nums[2][1] = 3;
        test(nums, n, y);
    }

    public static int test(int[][] nums, int n, int y) {
        if (n == 1) {
            return nums[0][1];
        }
        Arrays.sort(nums, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        Deque<Integer> deque = new LinkedList<>();
        int index = 0;//杀死野怪个数
        deque.offer(nums[index][1]); //生命值入队
        int j = index + 1; // 范围开始位置
        int len = nums[j - 1][0] + 2 * y; //技能会对[x-y,x+y]范围内的所有怪物造成1点伤害,相当于站在【i,len】的中间
        while (j < n && nums[j][0] <= len) {
            deque.offer(nums[j][1]); //生命值入队
            j++;
        }
        int res = 0;
        while (!deque.isEmpty()) {
            Integer val1 = deque.poll(); // 队列内第一个野怪的生命值
            if (val1 <= 0) {//说明该野怪在上一次已经被杀死，重新计算攻击范围
                index++; // 范围开始位置，假设每次只删除一个
                j = index + 1;
                if (j < n) {
                    len = nums[j - 1][0] + 2 * y; //技能会对[x-y,x+y]范围内的所有怪物造成1点伤害,相当于站在【i,len】的中间
                    while (j < n && nums[j][0] <= len) {
                        deque.offer(nums[j][1]); //生命值入队
                        j++;
                    }
                }
                if (deque.isEmpty() && j < n) {//说明队列内的已经全部被删除，且后面的不在之前的范围攻击内，需重新入队；
                    index = j;
                    deque.offer(nums[index][1]); //生命值入队
                    j = index + 1;
                    if (j < n) {
                        len = nums[j - 1][0] + 2 * y; //技能会对[x-y,x+y]范围内的所有怪物造成1点伤害,相当于站在【i,len】的中间
                        while (j < n && nums[j][0] <= len) {
                            deque.offer(nums[j][1]); //生命值入队
                            j++;
                        }
                    }
                }
            } else {
                res += val1;
                int size = deque.size();
                for (int i = 0; i < size; i++) {
                    Integer poll = deque.poll();// 先删除，再按序重新入队
                    deque.push(poll - val1);// 减去删除第一个元素所用的共计次数
                }
            }
        }
        System.out.println(res);
        return res;
    }
}

广联达 | #范围攻击#

题目描述：

输入描述

输出描述

复盘：贪心