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

· · 题解

题意

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

思路分析

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

复杂度分析

时间复杂度： O (N)，仅需遍历一次障碍物数组。 空间复杂度： O (N)，存储障碍物位置。

代码

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