5668888888888888
题面
我不想讲了(
思路
Level 1
分史莱姆组来吃!
每次能量够就吃一个史莱姆组!
Level 2
分组条件:
- 可以吃这个史莱姆组来回血
- 可以吃这个史莱姆组以逃脱
不断左右吃即可,吃到没史莱姆组为止。
Level 3
在统计组的时候,我们使用类似 two pointer 的解法来统计,同时统计出要吃这个组最少要多少生命。不能吃——NO。吃完——YES。
Level Boss
// 试试就逝世
#include <bits/stdc++.h>
using namespace std;
long long pre[200005];
long long a[200005];
vector<pair<long long, long long> > mleft, mright;
int main() {
int t;
scanf("%d", &t);
while (t--) {
mleft.clear();
mright.clear();
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
long long heal = a[k - 1];
a[k - 1] = 0;
for (int i = 0; i < n; i++) {
pre[i] = a[i] + (i ? pre[i - 1] : 0);
}
int l = k - 1, r = k - 1;
for (int i = k; i < n; i++) {
if (i == n - 1 || pre[i] >= pre[l]) {
long long worst = 0, cur = 0;
for (int j = l + 1; j <= i; j++) {
cur += a[j];
worst = min(worst, cur);
}
mright.emplace_back(cur, -worst);
l = i;
}
}
for (int i = k - 2; i >= 0; i--) {
if (i == 0 || pre[i - 1] <= pre[r - 1]) {
long long worst = 0, cur = 0;
for (int j = r - 1; j >= i; j--) {
cur += a[j];
worst = min(worst, cur);
}
mleft.emplace_back(cur, -worst);
r = i;
}
}
reverse(mleft.begin(), mleft.end());
reverse(mright.begin(), mright.end());
bool flag = 1;
while (mleft.size() && mright.size()) {
flag = 0;
if (mleft.back().second <= heal) {
heal += mleft.back().first;
mleft.pop_back();
flag = 1;
}
if (mright.back().second <= heal) {
heal += mright.back().first;
mright.pop_back();
flag = 1;
}
if (!flag) {
break;
}
}
if (flag) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}
标签:pre,mright,int,CF1734D,long,mleft,史莱姆
From: https://www.cnblogs.com/AProblemSolver/p/16729137.html