题解：P13517 [KOI 2025 #2] 障碍物

题意

本题要求我们以最小的移动次数跳过所有障碍物，其中每个障碍物必须通过跳跃动作越过。关键在于每次跳跃必须从障碍物前一格开始，并确保相邻障碍物之间的距离大于一。

思路分析

障碍物合法性检查：若存在两个相邻障碍物距离为 $1$ ，则无法跳过，直接输出 $-1$ 。
模拟移动过程：初始化当前位置为 $0$ ，移动次数为 $0$ 。遍历每个障碍物，计算从当前位置到障碍物前一格所需的步数。每到达一个障碍物前一格，执行一次跳跃，更新位置和移动次数。

复杂度分析

时间复杂度：

O (N)

，仅需遍历一次障碍物数组。空间复杂度：

O (N)

，存储障碍物位置。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int a[3000005];
int main() {
    int n,t;
    cin >> n;
    for(int i = 1;i < n;i ++){
    	scanf("%d",&t);
    	a[t] ++;
	}
    scanf("%d",&t);
   	a[t] ++;
   	int d = t;
    int ans = 0;
    for(int i = 0;i <= d;i ++){
        if(a[i]){
        	cout << -1;
        	return 0;
		}
		else if(a[i + 2]) ans ++;
		else ans ++,i ++;
    }
    cout << ans;
    return 0;
}

题解：P13517 [KOI 2025 #2] 障碍物

文章操作

题意

思路分析

复杂度分析

代码

相关推荐

评论

题解：P13517 [KOI 2025 #2] 障碍物