前言:
wa了无数发之后,才发现式子推错了。。。
修正推的式子之后,找最大值和最小值的位置又贪错了。。
不要熬夜改代码,因为思路可能就是错的思路,然后一直改,越改越错。
题目链接: D. Slime Escape
题意:
给定数组,还有起始位置k,初始体力为a[k],每到一个新的位置i,体力就+=a[i], 从k出发,如果能走到0或者n + 1,那就YES,否则NO;要求过程中,体力>=0。问是否能到达。
思路:
- 如果能直接走到0或者n+1,那就直接走过去。
- 如果一次性走不到终点,那么可以证明,每次走完之后,体力值一定不降。
于是就可以考虑,如果一直向右走,走到哪里会让体力值增加,且过程中体力值保证都>=0;
如果这个位置pos存在,那么他一定满足:(R是当前走过的地方的最右端)
sum[pos] - sum[R] >= 0
显然sum[pos]越大越好,但是还有一个条件要同时满足:(在过程中体力值都>=0)
val + sum[R ~ pos] - sum[R] >= 0
要满足这个限制条件,那就可以使sum[]最小,这样的话,式子的值就最小,如果式子的最小值都>=0,那么其他位置也一定是满足了条件的。
所以,找到最右的位置,满足这个限制条件后,进一步就能找到能够使得体力不减的位置了。
找这个最右位置的方法,那就是ST表+二分+前缀和:
固定左端点,枚举右端点,ST表查询这个区间的最小值,看看式子的值是否>=0.
得到这个最右点之后,直接ST表查询区间最大值,看看能否满足使得体力不减,如果可以,那就一直向右放心走就好了。
找到最大值后,我又用了一个笨蛋二分找他位置(其实可以一直向右了):
然后我找的也是最右边的,这个时候其实应该找的是最左边的了,所以又wa。稍微想想就明白了。
关于往左边走的
式子是:
val + sum[L - 1] - sum[pos - 1] >= 0
注意这里的是pos - 1,所以定义域变了,下面的二分的代码里,也都是要 - 1的,比如二分的时候是mid - 1,千万不要直接mid,不然会debug的很痛苦。
还有,ST表中查询位置应该从0开始。就是因为这里的-1.改一下板子就好了
剩下的应该都是细节性的问题了。
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
S.init(sum, n);
int L = k, R = k;
int val = a[k];
bool ok = 0;
int last = 1;
while(1)
{
int l = R, r = n;
// 还是这个式子,val + sum[pos] - sum[R] >= 0,想要这个式子不满足,那只要在中途中
// sum[pos]取最小值,如果合法,那就能继续向右扩展
while(l < r)
{
int mid = (l + r + 1) >> 1;
if (val + S.que_min(R, mid) - sum[R] >= 0) l = mid;
else r = mid - 1;
}
if (l == n) ok = 1;
int pos = l;
//在中间找一段sum[pos] - sum[R] >= 0,那么sum[pos]要求最大
int ma = S.que_max(R, pos);
if (ma - sum[R] >= 0) for (int i = R; ma != sum[i]; i++) R++;
// 要求 val + sum[L - 1] - sum[pos - 1] >= 0,取最大值,那这个式子就会最小
l = 1, r = L;
while(l < r)
{
int mid = (l + r) >> 1;
if (val + sum[L - 1] - S.que_max(mid - 1, L - 1) >= 0) r = mid;
else l = mid + 1;
}
if (l == 1) ok = 1;
pos = l;
//sum[L - 1] - sum[pos - 1] >= 0,取min,这个式子就最大
int mi = S.que_min(pos - 1, L - 1);
if (sum[L - 1] - mi >= 0) for (int i = L - 1; mi != sum[i]; i--) L--;
if (ok) break;
if (R - L + 1 == last) break;
last = R - L + 1;
val = sum[R] - sum[L - 1];
}
if (ok) cout << "YES\n";
else cout << "NO\n";
}