1007 Climb Stairs （贪心 | C思维）

题意

小明要爬一个n层的楼，每一层都一个生命值为hi的怪。只有小明的攻击力a>=血量h的时候才能消灭这只怪兽。如果小明消灭了这只怪兽，他会吸收他的生命值等量地转化为自己的攻击力。初始小明在第0层，有攻击力a0。

小明有两种行动方式

一是向上传送i格，i<=k；二是向下走1格。一个楼层不能被爬2次

现在小明想爬到楼顶并消灭所有的怪兽，问小明能不能办到。

思路

分段处理。由于题目要求必须把所有怪物打完，所以跳过的怪物还必须得走回去打败才行。我们要从当前位置x， 找到一个右端点r，使得可以按照r，r-1，r-2，x的顺序打败这一段的怪物。不难看出r更小的 时候不会更劣。

贪心。从后往前贪心。最远可以从 i + k - 1（相当于是小明跳到 i  + k - 1之后一直往下走，走到 i 还能在跳跃到 i + k 层） 开始贪心，贪不动了就重置value（跳过这个硬骨头一会处理，先处理当前a[i]这个硬骨头），缩小贪心的范围，目的是为了使value >= a[i],如果达不到就输出NO

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,w,k;
void solve()
{
    cin >> n >> w >> k;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++ ) cin >> a[i];
    for (int i = 1; i <= n; i++ ) {
        if(a[i] <= w) {
            w += a[i];
        } else {
            bool ok = false;
            int j = min(n, i + k - 1);
            int value = w;
            for (int z = j; z >= i; z -- ) {
                if(a[z] <= value) {
                    value += a[z];
                    if(z == i) {
                        ok = true;
                    }
                } else {
                    value = w;
                    j = z;// i = j;;
                }
            }
            if(ok) {
                i = j;
                w = value;
            } else {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}