Doveqise

Doveqise

万事皆虚,诸行皆允

CF1200B Block Adventure 题解

posted on 2019-08-12 20:17:36 | under 题解 |

这道题 一道简单贪心 CF的题质量都是很高的
我们可以得出一个贪心的结论:
当能拿方块的时候 尽可能多的拿方块
可以(显然法)证明 尽可能多的拿方块是不劣于少拿方块的
所以我们可以写出以下贪心代码
(当然你要判一下现在是不是走到了地底

#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");
    }
}