Fork me on GitHub

题解 CF1200B 【Block Adventure】

这个题实际上就是个贪心……题意我交了翻译,这里就不重复说了

很明显,由于包的容量是无限大的,所以我们只要能往包里塞砖块就往里面塞,因为多塞肯定不吃亏

于是得到贪心策略:能把当前的砖能拿的尽量拿走,如果高度不够补到打擦边球……

具体看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int t,n,m,k,h[105];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++)scanf("%d",&h[i]);
bool flag=1;//判断是否有解
for (int now=1;now<n&&flag;now++){
if (h[now]>=h[now+1]-k)m+=min(h[now]-h[now+1]+k,h[now]);//能拿则多拿,但注意只能拿空,不能那成负的\滑稽
else m-=h[now+1]-h[now]-k,h[now]=h[now+1]-k;//高度不够则补到刚好可以跳过去
if (m<0)flag=0;//砖头用完了都跳不过去,则肯定无解
}
puts(flag?"YES":"NO");
}
}