反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ

﹏ヽ暗。殇╰゛Y 2023-10-06 20:26 25阅读 0赞

## 反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ ##

#### 文章目录 ####

*  反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ
 *   *   *  问题：
         *  思路：
         *  代码：

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

最直接但错误的想法是：我们每回合开始时都可以尝试去进行攻击，这样能尽快杀死popo，如果接下来承受不住popo的进攻，我们或许可以放弃该回合的进攻，转为防守，即进行回血操作（设已经承受了popo造成的伤害attack，若奶量大于伤害，则回B点血，否则进行护卫，回attack点血）。但这种策略并不是贪心的策略，因为在不同的回合进行防守，赚的回血量不同，比如在popo的攻击为10000时，pipi没死，这回合不回血，在popo攻击为1时，pipi要死，这回合去回血，那就是亏惨了。那么最贪心的策略是什么呢？  
  我们可以使用反悔贪心策略，建立反悔机制。现实游戏中我们不能反悔，但是在程序中我们可以建立反悔机制，从而把之前做过的操作更改。我们的贪心策略是不断进攻使popo尽快死亡，若pipi血量不足再进行反悔进行最赚的回血操作。那么什么时候防守回血最赚，显然是在popo攻击力最高的那个回合。我们可以用优先队列保存popo每回合的攻击力，从大到小排序（大根堆），每回合pipi都先尝试攻击popo，若接下来pipi要死，则取出队头元素attack，在popo攻击力最高的那个回合进行反悔，攻转防，若奶量大于伤害，则回B点血，否则进行护卫，回attack点血，相应的，popo也要回A点血。

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static PriorityQueue<Attack> q = new PriorityQueue<>();
        public static void main(String[] args) {
        
            int n, i;
            long x, y, A, B, ai, maxAttack;
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            x = scanner.nextLong();
            y = scanner.nextLong();
            A = scanner.nextLong();
            B = scanner.nextLong();
            for (i = 0;i < n;i++) {
        
                y -= A;
                if (y <= 0) {
        
                    break;
                }
                ai = scanner.nextLong();
                q.add(new Attack(ai));
                if (x - ai <= 0 && !q.isEmpty()) {
        
                    maxAttack = q.poll().attack;
                    if (B > maxAttack) {
        
                        x += B;
                    } else {
        
                        x += maxAttack;
                    }
                    y += A;
                }
                x -= ai;
                if (x <= 0) {
        
                    break;
                }
            }
            if (y > 0) {
        
                System.out.println("Lose");
            } else {
        
                System.out.println("Win");
                System.out.println(i + 1);
            }
        }
    
    
    }
    
    class Attack implements Comparable<Attack> {
        
        public Long attack;
        public Attack(Long attack) {
        
            this.attack = attack;
        }
    
        @Override
        public int compareTo(Attack o) {
        
            return (int)(o.attack - this.attack);
        }
    }

代码中我创建了一个实现了Comparable接口的Attack类来保存popo的伤害值，是因为我发现在oj平台上在优先队列的构造函数里使用匿名内部类会报错`cannot infer type arguments for PriorityQueue<>`：  
![在这里插入图片描述][29c56700445e4f83b564b7527794c1d6.png]  
  如果有大佬知道这个报错是什么原因导致了，请在评论中指出，不胜感激

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/759ccab132d14b4b910740221c3b9bc2.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b598285386e74d2fa85759d0bd2e8ada.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[29c56700445e4f83b564b7527794c1d6.png]: https://img-blog.csdnimg.cn/29c56700445e4f83b564b7527794c1d6.png