此题主要也是通过模拟贪心的方式来得出是否满足条件,一共需要跳m次,每次跳b距离,所以跳跃则固定为mb,在L中其他的距离需要自己走,距离为L-mb,也就是说我们可以通过贪心的方式来求出至多可以走多少的距离,如果这个距离大于L-m*b,则代表我们必有方案可以走完,所以只需要求出贪心可走的最大距离,方式则为,从左至右遇到障碍则跳
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
一年一度的运动会到了,塔塔参加了障碍赛跑。
比赛的跑道是一条长度为L的直线,起点的坐标为x0=0,终点的坐标为xn+1=L。赛道上共有n障碍物,第i个障碍物位于xi=ai+0.5的位置。
作为一个人,塔塔可以跑步(x=x+1)也可以跳跃,每次跳跃的距离是一个固定的长度b,跳跃不会被障碍挡住(但是跑步会)。由于比赛规则的限制,他需要在比赛中完成恰好m次跳跃(只能往x坐标增大的方向跳,不能跳过终点,过了终点不能再起跳)。同时为了简化问题,我们假设塔塔只会在x坐标为整数的位置起跳。
现在塔塔想知道,是否存在一种方案使得他能够按照规则完成比赛?
本题中,每个测试点包含多组测试数据。
第一行一个整数T(1≤T≤105),表示数据的组数。
对于每组数据:
第一行四个整数n,L,m,b(1≤n≤105,1≤L,m,b≤109)含义如题面所示。
第二行有n个整数,第i个整数为a_i(0≤ai≤L)(1≤i≤n−1,ai<ai+1),含义如题面所示。
在单个测试点中,保证∑n≤2×105。
输出一个正整数代表万能门卡的张树。
输入
2
3 6 2 3
0 1 4
3 6 1 3
0 1 4
输出
YES
NO