D. Slime Escape(贪心/前缀和/模拟)

题目 参考

题意

给定n个数a[1],a[2],…a[n]，a[i]可正可负。一开始你位于第k个数，且a[k]>=0。现在，你要从第k个点，到达第0个位置，或者第n+1个位置。你的初始血量是cur=a[k]，每到达一个新的位置，你必须吸收它的能量值a[i]（但第2次经过这个点就没有了，因为被你吸掉了），即经过新的点i，你的当前血量更新为cur=cur+a[i]。

问，能否在血量一直保持非负的情况下，走出边界，到达点0或点n+1。

思路

贪心思路很容易想到。

• 向左扩展或向右扩展，看能否到达某个点，使得血量保持不减。
• 向左扩展或向右扩展，看能否到达对应的终点位置（0或者n+1）。

简单来讲，就是如果能扩展当前区域，且保持血量不减甚至增加，那肯定扩展区域，提供自己的防御力。 如果能一次性莽到终点，只要血量非负，牺牲点血量又如何，都取得胜利了。

具体怎么实现，我们可以用前缀和，维护向左、向右区间的可扩展的区间段。 详见代码

代码

#include 
using namespace std;
#define ll long long
const int maxn = 200010;
#define pll pair
void print_ve(const vector &v, string name) {
	cout