题目链接:
题目大意:植物大战僵尸。给定种植植物时间间隔t,以及每个僵尸的到达时间v,生命d。问是否能赢。
解题思路:
按照打完每只Zombie之后剩余时间v-d,从小到大排序。
理由如下:
设打完第i只Zombie的剩余时间为:$Remain(v,d)=V-i*t-D$
那么本题的目标函数为:$arg\max \limits_{i}\sum Remain(v,d)=V-i*t-D$
所以,应当尽可能把v-d较小的值放在i的前面,让Remain(v,d)尽可能大。
排序完之后,进行模拟,now=0,当前时间为0
从第1只Zombie算起,now+=t:
$if \quad Attack Time<D \quad then\quad GameOver$
注意,不可以取等,样例说明,正好到达位置被打死也会GameOver。
#include "cstdio"#include "algorithm"using namespace std;struct Zombie{ int v,d,idx; bool operator < (const Zombie &a) const { return v-d