题解 P1095 【守望者的逃离】

2018-02-23 21:16:18


题目标签是 贪心+DP,但是实际上我是贪心+模拟出来结果的(不知道是不是数据弱了,欢迎 $dalao$ 们 $hack$

题解中有关贪心的内容我都会把它加粗变♂大

定义一下 $s$ 是距离, $v=s/t$ 是单位时间的速度,使用闪现的时候是 $v=60/1=60$ ,正常行走的时候是 $v=17/1=17$ 。积攒一个闪现加上释放:最好情况是魔法在 $10$ 或以上, $v=60/1=60$ ;最坏情况是没有魔法:积攒和释放共需要 $4$ 秒,平均速度 $v$ 就是 $v=60/4=15$ 。

首先,有魔法( $=10$ )的时候,一定要用闪现,这时速度是最快的, $v=60$ ,这里是贪心的一个点,尽可能让速度快。

当魔法耗尽时( $<10$ ),有两种情况:

1.剩余 $0~1$ ,补充 $3$ 次魔法可以用闪现,平均速度是 $v=60/4=15$ ,能走 $60m$ ,耗费 $4$ 秒,但比行走慢;补充 $5$ 次魔法可以用两次闪现,平均速度是 $v=120/7=17.14$ ,能走 $120m$ ,耗费 $7$ 秒,比行走快。

2.剩余 $2~9$ ,补充 $1~2$ 次魔法后可以用一次闪现,平均速度分别是 $v=60/2=30,v=60/3=20$ ,耗费 $2$ 秒和 $3$ 秒,都比行走快。

因此,在以上两种情况中,离终点较远的情况下,闪现是比行走要快的,同理是贪心的思想。

除此之外,我们还要特判快到终点(定为 $s<68$ )的情况,利用表格来说明

剩余魔法 0~1 2~5 6~9 效果
使用1次闪现 耗时4s 耗时3s 耗时2s 距离60m
不使用闪现 耗时1s 耗时1s 耗时1s 距离17m

列出下一次闪现需要几秒恢复: $f(m)=(10-m-1)/4+2$ (算上使用的 $1s$ )向下取整

所以 $f(0)=4,s=60$ 而 $4s$ 可以走(正常行走) $68m$

$f(1)=4,$ $4s$ 可以走 $68m$

因此在 $t>=4$ 且 $s<68$ 时正常行走就可以出去

$f(2)=3,$ $4s$ 可以走 $51m $

$f(3)=3,$ $f(4)=3,$ $f(5)=3,$ $f(6)=2,$ $f(7)=2,$ $f(8)=2,$ $f(9)=2$ 均同理

以上判断方程为( $sum$ 是最终结果, $m$ 因为在 $while$ 循环中耗尽, $m<10$ )

$if((9-m)/4+2>=((s-1)/17+1))$

if(m<10&&t>=(s-1)/17+1&&(9-m)/4+2>=((s-1)/17+1))
    {
        t-=(s-1)/17+1;
        s=0;
        break;
    }

$(9-m)/4+2$ 是使用闪现所耗费的总时间

$((s-1)/17+1))$ 是行走耗费的总时间

行走耗时更少的话当然是选择行走了,因为可以拆成更少的时间段来进行,举个栗子

剩余魔法 $Δm$ $1$
剩余距离 $Δs$ $18$
剩余时间 $Δt$ $3$

可以看出,当 $Δs=18$ 时,只需2s就可以直接走出去了,而补充魔法用闪现需要 $4s$

这里当然是选择贪 $2s$ 了,这些思想在代码里都有体现。

Code:

#include<cstdio>
int main()
{
    int m,s,t,S,T;
    scanf("%d%d%d",&m,&s,&t);
    S=s;//S,T用来存初始值,方便最后一步算出结果
    T=t;
    while(s>0&&t>0)//循环的边界,也是最终判断的依据
    {
        if(m>=10)//当m>=10时,用闪现是最快的,没有之一,贪心思想
        {
            m-=10;
            s-=60;
            t--;
        }
        else if(m<10&&((9-m)/4+1)<t)//判断是休息还是直接开溜
        {
            if((9-m)/4+2>=((s-1)/17+1))//当能直接开溜的时候,贪心贪最小的
            {
                t-=(s-1)/17+1;
                s=0;
                break;
            }
            m+=4;
            t--;
        }
        else//不特判的情况,也不休息,直接正常行走,比如当t较小的时候
        {
            s-=17;
            t--;
        }
    }
    if(s<=0)
        printf("Yes\n%d\n",T-t);
    else if(t<=0)
        printf("No\n%d\n",S-s);
    return 0;
}