Codeforces Round #822 (Div. 2) D

https://codeforces.com/contest/1734/problem/D

题意

有 n 只史莱姆，每只都有一个值，其中第 k 只被你控制，你希望能走到 0 或 n + 1 这两个位置，也就是说遇到路上的史莱姆需要将他们吸收，即现有的值加上他们的值

路上任何时候值小于 0 都会导致游戏立即结束

问你是否存在胜利策略

思路

对于你当前处在的这个位置，你会选择向左走，当且仅当你能在此过程中获得增益，或者你可以活着走出去

选择向右走同理

code

设向左、向右走的最大边界为 L , R , 那么可以写出如下代码：(注意细节)

bool f = 0;   
int sL = 0, sR = 0;
ll now = a[k];
while(1){
  bool fla = 0;
  //向左走
  while(L > 1 && now + a[L - 1] + sL >= 0) {  //生命值满足还可以向左走的条件
    sL += a[L - 1];
    L--;
    if(sL > 0) {  //可以获得增益
      fla = 1;
      now += sL;
      sL = 0;
      break;
    }
  }
  //向右走
  while(R < n && now + a[R + 1] + sR >= 0) {  //生命值满足还可以向左走的条件
    sR += a[R + 1];
    R++;
    if(sR > 0) {  //可以获得增益
      fla = 1;
      now += sR;
      sR = 0;
      break;
    }
  }
  if(L == 1 || R == n) {
    f = 1;
    break;
  }
  if(!fla) break;
}
puts(f == 1 ? "YES" : "NO");