CF1200B Block Adventure 题解
Doveqise
2019-08-12 20:17:36
这道题 一道简单贪心 CF的题质量都是很高的
我们可以得出一个贪心的结论:
当能拿方块的时候 尽可能多的拿方块
可以(显然法)证明 尽可能多的拿方块是不劣于少拿方块的
所以我们可以写出以下贪心代码
(当然你要判一下现在是不是走到了地底
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e2+5;
int h[maxn];
signed main()
{
int t;
scanf("%d",&t);
for(int ti=1;ti<=t;ti++)
{
memset(h,0,sizeof(h));
int n,m,k,flg=0;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
for(int i=1;i<n;i++)
{
if(h[i]>=max(h[i+1]-k,0))
{
m+=h[i]-max(h[i+1]-k,0);
continue;
}
else if(h[i+1]-k>h[i]+m)
{
puts("NO");
flg=1;
break;
}
else
{
m-=h[i+1]-h[i]-k;
continue;
}
}
if(flg)
continue;
else
puts("YES");
}
}
```