- 反悔贪心 + 优先队列: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 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 { 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<>:
如果有大佬知道这个报错是什么原因导致了,请在评论中指出,不胜感激
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)