题解 CF1200B 【Block Adventure】
引领天下
2019-08-12 18:01:37
这个题实际上就是个贪心……题意我交了翻译，这里就不重复说了
很明显，由于包的容量是无限大的，所以我们只要能往包里塞砖块就往里面塞，因为多塞肯定不吃亏
于是得到贪心策略：能把当前的砖能拿的尽量拿走，如果高度不够补到打擦边球……
具体看代码吧
```cpp
#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");
}
}
```