CF637D Running with Obstacles 题解

发布于 2020-09-02  668 次阅读


实际已有的题解已经把大体思路阐述出来了,但我认为缺少很多对细节的解答,故再写了一篇。

题意

题目链接

大体题意不再阐述,这里有几点需要注意,首先,跳跃后到达的那一格是不算助跑距离的。其次,能跳跃 $d$ 个单位不是跨越过 $d$ 个单位,而是在当前位置的基础上前进 $d$ 个单位。

解析

首先看到数据范围,很容易想到此题是 dp 或者贪心。

然后我们发现,跑道上有若干个障碍,而运动员想要跳跃需要一定的助跑距离,那我们只要让这个助跑距离尽可能大,就更有机会跳过去,因此我们确定这道题的思路为贪心。

我们很容易想到,每次在障碍的前一个单位跳跃,在障碍的后一个单位落下,可以使中间没有障碍的那一段助跑距离尽可能大。当我们这样求出所有障碍之间的最大助跑距离后,仍然有一些障碍之间的助跑距离是不够的,我们可以将这种障碍合在一起,作为一个大障碍考虑。

大体思路如上,但作为一道 CF 的毒瘤题,我们接着还需要通过部分代码来说明几个注意点。

预处理

scanf("%lld%lld%lld%lld",&n,&m,&s,&d);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    if(a[1]-1<s){
        printf("IMPOSSIBLE\n");
        return 0;
    }
    a[0]=-(1e9+7);
    for(int i=1;i<=n;i++){
        if(a[i]-a[i-1]-1>s) e[++cnt].l=a[i],e[cnt].r=a[i];
        else e[cnt].r=a[i];
    } 

这里有几个非常重要的注意点!一不小心就错了。

首先,我们预处理是从 $1$ 号障碍开始的,因此如果刚开始助跑距离就不够,直接输出 IMPOSSIBLE 即可。

其次,一定要把 $a_0$ 的初值设为无穷小,因为第一个障碍一定要形成一个独立的大障碍,不可能也不能存在其与 $a_0$ 相连的情况。

另外别忘了障碍不一定是有序的,需要先排序。

寻找答案

for(int i=1;i<=cnt;i++)
        if(e[i].r-e[i].l+1>=d){
            printf("IMPOSSIBLE\n");
            return 0;
        }
    int now=0;
    for(int i=1;i<=cnt;i++){
        if(e[i].l!=1){
            printf("RUN %lld\n",e[i].l-1-now);
            printf("JUMP %lld\n",e[i].r+1-(e[i].l-1));
            now=e[i].r+1;
        }
    }
    if(now<m)  printf("RUN %lld\n",m-now);

这部分相对简单,主要注意当障碍长度等于 $d$ 时,是无法跳跃过去的(在题意中阐述了原因);以及如果最终无法到终点,还需要跑几步就可以了。

代码都在上边呈现了,不再赘述。


月流华 岁遗沙 万古吴钩出玉匣