[Luogu]P1095 守望者的逃离
本文最后更新于 294 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp1095/

题意描述

题目传送门

题目大意:有初始魔法值 $M$ 点,时间 $T$ 秒,要走距离为 $S$,问能否顺利完成。
每秒有三种情况:

  1. 占用当前秒,行走 $17$ 米。
  2. 占用当前秒,花费 $10$ 点魔力,传送 $60$ 米。
  3. 占用当前秒,恢复 $4$ 点魔力。

解法

看到题目第一时间打开计算器,计算一下传送速度……
可以发现,一次传送需要 $2.5$ 秒的时间恢复的魔力,而传送又占用 $1$ 秒,总耗时 $3.5$ 秒,距离为 $60$ 米。

60/3.5

一路传送法

均摊下来是比走的快的!那好,一路死命传送,到最后不够传送的时间再走就好了!
凑一个整数周期,$7$ 秒传送 $2$ 次,最后剩下时间走路!
然而问题来了,有初始魔力这种东西,怎么处理我并没有想到……

传比跑好法

此时如果你偷偷瞟一眼题解,会发现题解中提到了 传送和跑步一起进行 的说法,顿开茅塞!

好!我懂了!我会了!自己做出来的!

可以发现,即使初始魔力为零,一直传送在理想情况下还是比跑步快,何况初始魔力还有值呢。
什么时候更快呢?肯定是每次传送之后就比跑步快了!(确信)
于是在传送后将传送的路程赋值给跑步的路程,乱打得到代码:

#include <cstdio>
using namespace std;
int m,s,t;
int s1,s2;
int main()
{
    scanf("%d%d%d",&m,&s,&t);
    for(int i = 1;i<=t;++i)
    {
        s1 += 17;
        if(m >= 10)
            s2 += 60,m -= 10,s1 = s2;
        else
            m += 4;
        if(s1 >= s)
        {
            printf("Yes\n%d",i);
            return 0;
        }
    }
    printf("No\n%d",s1);
    return 0;
}

交上去之后可以得到 $90$ 分的好成绩,但是第九个点 WA 了,到底是为什么呢……

HACK

事实上,并不是每次传送之后一定比跑步快的。
因为秒只能是整秒,那么需要 $3$ 秒才能攒够一次传送的魔力,最后需要 $4$ 秒才能进行一次传送,传送 $60$ 米的距离。
而如果这 $4$ 秒直接拿来跑步,反而可以跑出 $68$ 米的好成绩,吊打传送。
所以武断地认为传送后一定比跑步快是错误的。

比跑步快就传送法

直接每次传送就以为传送快是不行的,那是否可以当传送快的时候就换传送呢?
思考一下,是可以的。
首先,已知的是,一直传送理论上是比跑步快的。
而解题方法可以类比为后台开两个线程:

线程1: 一直跑步。
线程2: 一直传送。

而在线程2单次传送过后,检测线程1的距离,如果小于线程2,那么可以直接将线程1前面跑的路全当成无用功,替换为全是传送的路程。

#include <cstdio>
using namespace std;
int m,s,t;
int s1,s2;
int main()
{
    scanf("%d%d%d",&m,&s,&t);
    for(int i = 1;i<=t;++i)
    {
        s1 += 17;
        if(m >= 10)
            s2 += 60,m -= 10,s1=(s2>s1?s2:s1);
        else
            m += 4;
        if(s1 >= s)
        {
            printf("Yes\n%d",i);
            return 0;
        }
    }
    printf("No\n%d",s1);
    return 0;
}

DONE.

本文标题:[Luogu]P1095 守望者的逃离
本文作者:Clouder
本文链接: https://www.codein.icu/lp1095/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇