给定两个数组x和hp，长度都是N。 x数组一定是有序的，x[i]表示i号怪兽在x轴上的位置 hp数组不要求有序，hp[i]表示i号怪兽的血量

墨蓝 2024-03-27 08:49 36阅读 0赞

#### 目录 ####

*   *  题目描述
     *  题目分析
     *  贪心
     *  贪心+线段树
     *  对数器测试
     *  效率对比
     *  避坑问题

### 题目描述 ###

> 给定两个数组x和hp，长度都是N。  
> x数组一定是有序的，x\[i\]表示i号怪兽在x轴上的位置  
> hp数组不要求有序，hp\[i\]表示i号怪兽的血量  
> 为了方便起见，可以认为x数组和hp数组中没有负数。  
> 再给定一个正数range，表示如果法师释放技能的范围长度(直径！)  
> 被打到的每只怪兽损失1点血量。  
> 返回要把所有怪兽血量清空，至少需要释放多少次aoe技能？  
> 三个参数：int\[\] x, int\[\] hp, int range  
> 返回：int 次数

### 题目分析 ###

**贪心**  
我们先假设hp是紧贴在站在一起的（也就是先不看X），假设其hp如下：  
![在这里插入图片描述][1db21dd4e017499ab60f8e7894a13a5f.png]  
因为最终要把所有的怪兽都杀死。

*  我们先看第一个怪兽，其hp为5。那么不管这个怪兽是怎么死的，其一定要被AOE覆盖它5次。  
    \-我们每次AOE以它为起点，放五次，那么hp数组变为：  
    ![在这里插入图片描述][3582e54c41ac43d5ae360ba603f7f6e8.png]
 *  然后我们再找下一个大于0的怪兽，以它作为AOE的起点，以最少的次数去杀死它，得到如下：  
    ![在这里插入图片描述][a01f3f387ee04d85adee200b4191430d.png]
 *  然后我们再找下一个大于0的怪兽，以它作为AOE的起点，以最少的次数去杀死它，得到如下：  
    ![在这里插入图片描述][a5745ec1d11e44449f635d996f4bdb1b.png]\- 下一个没有大于0的怪兽了，完毕。最终得到

### 贪心 ###

举个例子：
    如果怪兽情况如下，
    怪兽所在，x数组  : 2 3 5 6 7 9
    怪兽血量，hp数组 : 2 4 1 2 3 1
    怪兽编号        : 0 1 2 3 4 5
    技能直径，range = 2
    int n = x.length;
    int[] cover = new int[n];
    首先求cover数组，
    如果技能左边界就在0号怪兽，那么技能到2号怪兽就覆盖不到了
    所以cover[0] = 2;
    如果技能左边界就在1号怪兽，那么技能到3号怪兽就覆盖不到了
    所以cover[1] = 3;
    如果技能左边界就在2号怪兽，那么技能到5号怪兽就覆盖不到了
    所以cover[2] = 5;
    如果技能左边界就在3号怪兽，那么技能到5号怪兽就覆盖不到了
    所以cover[3] = 5;
    如果技能左边界就在4号怪兽，那么技能到6号怪兽（越界位置）就覆盖不到了
    所以cover[4] = 6(越界位置);
    如果技能左边界就在5号怪兽，那么技能到6号怪兽（越界位置）就覆盖不到了
    所以cover[5] = 6(越界位置);
    综上：
    如果怪兽情况如下，
    怪兽所在，x数组  : 2 3 5 6 7 9
    怪兽血量，hp数组 : 2 4 1 2 3 1
    怪兽编号        : 0 1 2 3 4 5
    cover数组情况   : 2 3 5 5 6 6
    技能直径，range = 2
    cover[i] = j，表示如果技能左边界在i怪兽，那么技能会影响i...j-1号所有的怪兽
    就是如下的for循环，在求cover数组

public static int minAoe2(int[] x, int[] hp, int range){
        
            int N = x.length;
            int[] cover = new int[N];
            int r = 0;
            for (int i = 0; i < N; i++) {
        
                while (r<N && x[r]-x[i]<=range){
        
                    r++;
                }
                cover[i] = r;
            }
            int ans = 0;
            for (int i = 0; i < N; i++) {
        
                int minus = hp[i];
                if (hp[i]>0){
        
                    for (int j = i; j < cover[i]; j++) {
        
                        hp[j] -= minus;
                    }
                    ans += minus;
                }
            }
            return ans;
        }

### 贪心+线段树 ###

// 关键点就是：
        // 1) 线段树
        // 2) 总是用技能的最左边缘刮死当前最左侧的没死的怪物
        // 3) 然后向右找下一个没死的怪物，重复步骤2)
        public static int minAoe3(int[] x, int[] hp, int range) {
        
            int n = x.length;
            int[] cover = new int[n];
            int r = 0;
            for (int i = 0; i < n; i++) {
        
                while (r<n && x[r]-x[i]<=range){
        
                    r++;
                }
                cover[i] = r;
            }
            SegmentTree st = new SegmentTree(hp);
            st.build(1,n,1);
            int ans = 0;
            for (int i = 1; i <= n; i++) {
        
                int leftHP = st.query(i,i,1,n,1);
                if (leftHP>0){
        
                    ans+=leftHP;
                    st.add(i,cover[i-1],-leftHP,1,n,1);
                }
            }
            return ans;
        }
    
        public static class SegmentTree{
        
            private int MAXN;
            private int[] arr;
            private int[] sum;
            private int[] lazy;
    
            public SegmentTree(int[] origin){
        
                int MAXN = origin.length+1;
                arr = new int[MAXN];  // arr[0] 不用 从1开始使用
                for (int i = 1; i < MAXN; i++) {
        
                    arr[i] = origin[i-1];
                }
                sum = new int[MAXN<<2];
                lazy = new int[MAXN<<2];
            }
    
            // 在初始化阶段，先把sum数组，填好
            // 在arr[l~r]范围上，去build，1~N，
            // rt : 这个范围在sum中的下标
            public void build(int l,int r,int rt){
        
                if (l==r){
        
                    sum[rt] = arr[l];
                    return;
                }
                int mid = (l+r) >> 1;
                build(l,mid,rt<<1);
                build(mid+1,r,rt<<1|1);
                pushUp(rt);
            }
    
            private void pushUp(int rt) {
        
                sum[rt] = sum[rt<<1] + sum[rt<<1 |1];
            }
    
            // L~R, C 任务！
            // rt，l~r
            public void add(int L,int R,int C,int l,int r,int rt){
        
                // 任务如果把此时的范围全包了！
                if (L<=l && r<=R){
        
                    sum[rt] += C *(r-l+1);
                    lazy[rt] += C;
                    return;
                }
                int mid = (l+r)>>1;
                pushDown(rt,mid-l+1,r-mid);
                if (L <= mid){
          //1-500 mid=250 但是我们要add 3-800    那么左边继续分
                    add(L,R,C,l,mid,rt<<1);
                }
                if (R>mid){
        
                    add(L,R,C,mid+1,r,rt<<1|1);
                }
                pushUp(rt);
            }
    
            // L~R, C 任务！
            // rt，l~r
            public int query(int L,int R,int l,int r,int rt){
        
                // 任务如果把此时的范围全包了！
                if (L<=l && r<=R){
        
                    return sum[rt];
                }
                int mid = (l+r)>>1;
                pushDown(rt,mid-l+1,r-mid);
                int ans = 0;
                if (L <= mid){
          //1-500 mid=250 但是我们要add 3-800    那么左边继续分
                    ans += query(L,R,l,mid,rt<<1);
                }
                if (R>mid){
        
                    ans += query(L,R,mid+1,r,rt<<1|1);
                }
                return ans;
            }
    
            private void pushDown(int rt, int ln, int rn) {
        
                if (lazy[rt] != 0){
        
                    lazy[rt<<1] += lazy[rt];
                    lazy[rt<<1|1] += lazy[rt];
                    sum[rt<<1] += lazy[rt]*ln;
                    sum[rt<<1|1] += lazy[rt]*rn;
                    lazy[rt] = 0;
                }
            }
    
    
        }

### 对数器测试 ###

package com.donglin.class01;
    
    import java.util.Arrays;
    
    public class AOE {
        
    
        // 纯暴力解法
        // 太容易超时
        // 只能小样本量使用
        public static int minAoe1(int[] x, int[] hp, int range) {
        
            boolean allClear = true;
            for (int i = 0; i < hp.length; i++) {
        
                if (hp[i] > 0) {
        
                    allClear = false;
                    break;
                }
            }
            if (allClear) {
        
                return 0;
            } else {
        
                int ans = Integer.MAX_VALUE;
                for (int left = 0; left < x.length; left++) {
        
                    if (hasHp(x, hp, left, range)) {
        
                        minusOneHp(x, hp, left, range);
                        ans = Math.min(ans, 1 + minAoe1(x, hp, range));
                        addOneHp(x, hp, left, range);
                    }
                }
                return ans;
            }
        }
    
        public static boolean hasHp(int[] x, int[] hp, int left, int range) {
        
            for (int index = left; index < x.length && x[index] - x[left] <= range; index++) {
        
                if (hp[index] > 0) {
        
                    return true;
                }
            }
            return false;
        }
    
        public static void minusOneHp(int[] x, int[] hp, int left, int range) {
        
            for (int index = left; index < x.length && x[index] - x[left] <= range; index++) {
        
                hp[index]--;
            }
        }
    
        public static void addOneHp(int[] x, int[] hp, int left, int range) {
        
            for (int index = left; index < x.length && x[index] - x[left] <= range; index++) {
        
                hp[index]++;
            }
        }
    
    
        public static int minAoe2(int[] x, int[] hp, int range){
        
            int N = x.length;
            int[] cover = new int[N];
            int r = 0;
            for (int i = 0; i < N; i++) {
        
                while (r<N && x[r]-x[i]<=range){
        
                    r++;
                }
                cover[i] = r;
            }
            int ans = 0;
            for (int i = 0; i < N; i++) {
        
                int minus = hp[i];
                if (hp[i]>0){
        
                    for (int j = i; j < cover[i]; j++) {
        
                        hp[j] -= minus;
                    }
                    ans += minus;
                }
            }
            return ans;
        }
    
    
        // 正式方法
        // 关键点就是：
        // 1) 线段树
        // 2) 总是用技能的最左边缘刮死当前最左侧的没死的怪物
        // 3) 然后向右找下一个没死的怪物，重复步骤2)
        public static int minAoe3(int[] x, int[] hp, int range) {
        
            int n = x.length;
            int[] cover = new int[n];
            int r = 0;
            for (int i = 0; i < n; i++) {
        
                while (r<n && x[r]-x[i]<=range){
        
                    r++;
                }
                cover[i] = r;
            }
            SegmentTree st = new SegmentTree(hp);
            st.build(1,n,1);
            int ans = 0;
            for (int i = 1; i <= n; i++) {
        
                int leftHP = st.query(i,i,1,n,1);
                if (leftHP>0){
        
                    ans+=leftHP;
                    st.add(i,cover[i-1],-leftHP,1,n,1);
                }
            }
            return ans;
        }
    
        public static class SegmentTree{
        
            private int MAXN;
            private int[] arr;
            private int[] sum;
            private int[] lazy;
    
            public SegmentTree(int[] origin){
        
                int MAXN = origin.length+1;
                arr = new int[MAXN];  // arr[0] 不用 从1开始使用
                for (int i = 1; i < MAXN; i++) {
        
                    arr[i] = origin[i-1];
                }
                sum = new int[MAXN<<2];
                lazy = new int[MAXN<<2];
            }
    
            // 在初始化阶段，先把sum数组，填好
            // 在arr[l~r]范围上，去build，1~N，
            // rt : 这个范围在sum中的下标
            public void build(int l,int r,int rt){
        
                if (l==r){
        
                    sum[rt] = arr[l];
                    return;
                }
                int mid = (l+r) >> 1;
                build(l,mid,rt<<1);
                build(mid+1,r,rt<<1|1);
                pushUp(rt);
            }
    
            private void pushUp(int rt) {
        
                sum[rt] = sum[rt<<1] + sum[rt<<1 |1];
            }
    
            // L~R, C 任务！
            // rt，l~r
            public void add(int L,int R,int C,int l,int r,int rt){
        
                // 任务如果把此时的范围全包了！
                if (L<=l && r<=R){
        
                    sum[rt] += C *(r-l+1);
                    lazy[rt] += C;
                    return;
                }
                int mid = (l+r)>>1;
                pushDown(rt,mid-l+1,r-mid);
                if (L <= mid){
          //1-500 mid=250 但是我们要add 3-800    那么左边继续分
                    add(L,R,C,l,mid,rt<<1);
                }
                if (R>mid){
        
                    add(L,R,C,mid+1,r,rt<<1|1);
                }
                pushUp(rt);
            }
    
            // L~R, C 任务！
            // rt，l~r
            public int query(int L,int R,int l,int r,int rt){
        
                // 任务如果把此时的范围全包了！
                if (L<=l && r<=R){
        
                    return sum[rt];
                }
                int mid = (l+r)>>1;
                pushDown(rt,mid-l+1,r-mid);
                int ans = 0;
                if (L <= mid){
          //1-500 mid=250 但是我们要add 3-800    那么左边继续分
                    ans += query(L,R,l,mid,rt<<1);
                }
                if (R>mid){
        
                    ans += query(L,R,mid+1,r,rt<<1|1);
                }
                return ans;
            }
    
            private void pushDown(int rt, int ln, int rn) {
        
                if (lazy[rt] != 0){
        
                    lazy[rt<<1] += lazy[rt];
                    lazy[rt<<1|1] += lazy[rt];
                    sum[rt<<1] += lazy[rt]*ln;
                    sum[rt<<1|1] += lazy[rt]*rn;
                    lazy[rt] = 0;
                }
            }
    
    
        }
    
    
        // 为了测试
        public static int[] randomArray(int n, int valueMax) {
        
            int[] ans = new int[n];
            for (int i = 0; i < n; i++) {
        
                ans[i] = (int) (Math.random() * valueMax) + 1;
            }
            return ans;
        }
    
        // 为了测试
        public static int[] copyArray(int[] arr) {
        
            int N = arr.length;
            int[] ans = new int[N];
            for (int i = 0; i < N; i++) {
        
                ans[i] = arr[i];
            }
            return ans;
        }
    
        // 为了测试
        public static void main(String[] args) {
        
            int N = 50;
            int X = 500;
            int H = 60;
            int R = 10;
            int testTime = 50000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
        
                int len = (int) (Math.random() * N) + 1;
                int[] x2 = randomArray(len, X);
                Arrays.sort(x2);
                int[] hp2 = randomArray(len, H);
                int[] x3 = copyArray(x2);
                int[] hp3 = copyArray(hp2);
                int range = (int) (Math.random() * R) + 1;
                int ans2 = minAoe2(x2, hp2, range);
                int ans3 = minAoe3(x3, hp3, range);
                if (ans2 != ans3) {
        
                    System.out.println("出错了！");
                }
            }
            System.out.println("测试结束");
    
            N = 500000;
            long start;
            long end;
            int[] x2 = randomArray(N, N);
            Arrays.sort(x2);
            int[] hp2 = new int[N];
            for (int i = 0; i < N; i++) {
        
                hp2[i] = i * 5 + 10;
            }
            int[] x3 = copyArray(x2);
            int[] hp3 = copyArray(hp2);
            int range = 10000;
    
            start = System.currentTimeMillis();
            System.out.println(minAoe2(x2, hp2, range));
            end = System.currentTimeMillis();
            System.out.println("运行时间 : " + (end - start) + " 毫秒");
    
            start = System.currentTimeMillis();
            System.out.println(minAoe3(x3, hp3, range));
            end = System.currentTimeMillis();
            System.out.println("运行时间 : " + (end - start) + " 毫秒");
        }
    
    }

### 效率对比 ###

下面是使用了线段树，时间复杂度O(NlogN)  
![在这里插入图片描述][88500ee2229e45f39e5f371d474bfb33.png]

### 避坑问题 ###

树的跟节点root，那么右孩子为2\*root+1  
当你想要使用<<的时候注意了，root<<1 | 1或者(root<<1)+1 ,不要写成root<<1 + 1

> | 是位运算符  
> ||是逻辑运算符  
> \+的优先级大于<<

[1db21dd4e017499ab60f8e7894a13a5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1486b3164bf542778de605b6b15f3e30.png
[3582e54c41ac43d5ae360ba603f7f6e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dc2bd429de2b4c1b811b424c5e08cf7b.png
[a01f3f387ee04d85adee200b4191430d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7d9e1d2e1d424840a8090986031ab305.png
[a5745ec1d11e44449f635d996f4bdb1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/697521eaf2344d73b8cbe58ff2d0e9f7.png
[88500ee2229e45f39e5f371d474bfb33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cc90317590594cc9bdf36a82f36ba8ee.png