题解：CF637D Running with Obstacles

_czl_ · 2026-07-21 20:38:04 · 题解

贪心。在 DP 题单里找的，以为是 DP。

设当前的位置为 x。

题意很明确，先排序，从 1 往后处理。贪心尽可能往前跑，跑到前方是障碍点就跳，有几个判断不可行的点：

• 助跑距离不够，a_i-x-1 < s，即障碍到你所在的点不够助跑，永远无法到达。
• 存在连续很多个障碍，能助跑但是障碍连续超过 d 个，跳不过去。

有个细节，最后如果跳完还没到终点，还要加上最后的距离，代码非常好写。

::::info[代码]

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define pll pair<int,int>
using namespace std;

inline int read() {
    int res=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
    return res*f;
}

inline void write(int x) {
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

const int maxn=2e5+5;

int n,m,s,d;
int a[maxn];

struct node {
    string op;
    int val;
};
vector<node> ans;

signed main() {

    n=read(),m=read(),s=read(),d=read();

    for(int i=1;i<=n;i++) a[i]=read();

    sort(a+1,a+n+1);

    int cur=0,i=1;   

    while(i<=n) {

        if(a[i]-1-cur<s) {

            puts("IMPOSSIBLE");
            return 0;
        }

        if(a[i]-1-cur>0) ans.push_back({"RUN",a[i]-1-cur});

        int j=i;

        while(j+1<=n && a[j+1]-a[j]-2<s) j++;

        int dis=(a[j]+1)-(a[i]-1);

        if(dis>d) {

            puts("IMPOSSIBLE");
            return 0;
        }

        ans.push_back({"JUMP",dis});
        cur=a[j]+1;

        i=j+1;
    }

    if(m-cur>0) ans.push_back({"RUN",m-cur});

    for(auto x:ans) {
        cout<<x.op<<" ";
        write(x.val),putchar('\n');
    }

    return 0;
}

::::