题解 CF1200B 【Block Adventure】

发表于 更新于 阅读次数： Waline： 阅读次数：
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");
    }
}