本场比赛写出一个 1007 也写一篇题解吧！

1007

题目描述

题目分析

就是给你 $n$ 层楼，每层楼有一个怪物，杀了怪物需要自己的攻击力超过它的血量，否则不能到达该楼层，一次可以跳 $k$ 以内的层或者下降一层，杀了怪物后这一层不能继续呆了，杀了怪物之后怪物的血量会成为自己的攻击力。

看标程是线段树写的，咱也不会，只能纯模拟啦。

首先可以肯定的一点就是：你跳了之后要把下面的怪物都收拾完，因为题目问你的是：能否解决所有怪物！！而你一次只能下降一层，不能去已经没有怪物的楼层。因此我们主要关注，我们要跳到哪里去，能收拾完下面的怪物。首先可以肯定的是：直接选择能跳的跳是肯定不行的，随便出一组数据便可知。

1
2
3
1
6 1 5
6 1 1 2 1 4

当你贪心地跳到第 $2$ 层之后你就会发现 $6$ 你收拾不了了。而这个数据是有解的，我们跳到第五层从上往下收拾完是能打过 $6$ 的。

那么其实我们就需要判断：我们跳了一个楼层之后是否能收拾下面的怪物，收拾下面的怪物是从上往下收拾，我们还可以沿途吃掉中间的怪物增长攻击力，但是这样的 check 乍一听好像是 O(n) 啊，不可行！但是其实我们可以把打不过的怪物堆起来，打得过的怪物直接扔掉，如果这次选择这层楼打不掉，那么我们选择更高的楼层去打。这样在整体的判断中，每个怪物只会被判一次，总时间复杂度能接受。

具体实现方式我们可以用栈，首先如果当前楼层我能打过我肯定直接打了，因为上一层比不上一层打肯定要好的，上了一层我还能多一个选择。那么如果当前打不过，我们就先压栈，循环k以内的数据，如果能打过，尝试过来打，并开始从栈中取出怪物来看看能否打过，能打过扔出来，打不过则继续往上走。那么不难发现，我们如果跳到了 $p$ 层，要判断能否结局 $p-i$ 层的怪物我们只需要把当前攻击力加上 $p-i+1——p$ 的怪物数值之和能否超过它的血量即可。那么这里算到和的话我们就可以前缀处理了。那么为什么不需要重复判断呢？因为我跳到这一层时，我都能打过这个怪物了，我跳到更高的层来打这个怪物会打不过？

如果说 $k$ 层遍历完了之后，我栈里面还有数据，说明我跳哪都打不完这些怪物，就放弃了。如果能跳 $p$ 层打过，我当前在 $q$ 层的话，那么我在解决完之后我身处 $q+1$ 层，中间 $q+1——p$ 层都是空楼层，都不能去，因此我们把自己放到 $p$ 层，但是同时可选择的范围要随着之前跳的高度减少。因为我原来在 $q+1$ 层本来也就只能跳到 $q+k$ 层嘛，这个应该很好理解。

那么看完这些之后，相信你不难理解下面的标程了。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define maxn 200005
#define int long long
using namespace std;
int a[maxn],pre[maxn];
char s[maxn];
int n,m,k;

void solve(){
    scanf("%lld%lld%lld",&n,&m,&k);
    int sum=m;
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        sum+=a[i];
    }
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    int now=0;
    stack<pair<int,int>>s;
    int len=1;
    //printf("%d\n",m);
    for(int i=1;i<=n;i++){
        if(m<a[i]){
            for(int j=i;j<=min(n,i+k-len);j++){
                
                if(m>=a[j]){
                    while(s.size()){
                        auto top=s.top();
                        if(m+pre[j]-pre[top.second]>=a[top.second]){
                            s.pop();
                            continue;
                        }
                        break;
                    }
                    if(s.empty()){
                        m+=pre[j]-pre[i-1];
                        len=j-i+1;
                        i=j;
                        break;
                    }
                }
                else{
                    s.push({a[j],j});
                }    
            }
        }
        else {
            m+=a[i];
            len=1;
        }
        
        if(s.size()){
            puts("NO");
            return ;
        }
    } 
    if(m!=sum){
        puts("NO");
    }
    else{
        puts("YES");
    }
    
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}