【官方题解】贪心

【题目大意】

m个落脚点位于不同位置，超楠要从初始为1的位置跳到n每次只能跳 $1 \sim k$ 中的任意值并且要跳到落脚点（或n）题目要求计算最少跳跃次数，如果无法到达则输出 -1。

Subtask1: 100%

【算法分析】

本题采用贪心算法

$m$ 个落脚点存在数组 $1 \sim n$ 中并且同时将起点终点存入数组即数组 $0$ 位置标 $1$ ， $m+1$ 标记 $n$ ，判断是否有两点差距大于k，如果大于k说明无法达到终点输出-1；
我们可以用一个标记记录超楠此时所在位置，循环向下扫描直到扫描到 $a_i$ 与超楠所在位置距离大于 $k$ 时，超楠就需要跳到 $a_{i-1}$ 的位置，并记录超楠跳跃次数，注意最后超楠可能并没有跳到 $n$ 所以我们要判断跳跃次数加 $1$ 。

时间复杂度 O(n) 。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,a[500005],dp[500005];

int main(){
	cin>>n>>m>>k;
	a[0]=1,a[m+1]=n;
	ll f=1;
	for (int i=1;i<=m+1;i++) {
		if (i<=m) cin>>a[i];
		if (a[i]-a[i-1]>k) f=0;
	}
	if (!f){
		cout<<-1;
		return 0;
	}
	ll last=1,c=0;
	for (int i=1;i<=m+1;i++){
		if (a[i]-last>k){
			last=a[i-1];
			c++;
		}
	}
	if (last!=n) c++;
	cout<<c;
	
	return 0;
}