反悔贪心 + 优先队列：PIPI的逃跑路线Ⅳ-蒲公英云

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

文章目录

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

问题：

在这里插入图片描述

思路：

最直接但错误的想法是：我们每回合开始时都可以尝试去进行攻击，这样能尽快杀死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<>：
在这里插入图片描述
如果有大佬知道这个报错是什么原因导致了，请在评论中指出，不胜感激