本场比赛写出一个 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;
}