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");
标签:sR,向左走,Codeforces,break,sL,fla,Div,now,822
From: https://www.cnblogs.com/re0acm/p/16726237.html