B3768 [语言月赛202305] 独行题解

· · 题解

Source & Knowledge

2023 年 5 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

一艘船以 v_{0} 的速度向距离为 S 的目的地行驶，在给出的时间点 T_{i}，这艘船会掉头行驶，掉头行驶的初始速度是 v_{1}，初始时间是 t_{1}。之后的每一次掉头，速度会在前一次的基础上增加 v_{2}，时间会在前一次的基础上增加 t_{2}。如果调头行驶时到了出发点，剩下的时间就原地不动。求到达目的地的时间（向上取整）。

题目分析

这一题的题面比较长，考察问题理解能力和代码实现能力。

（结尾有彩蛋）。

首先，我们快速地抓住题目大意。大致可以分为以下几步进行：

第一步，我们要知道这道题从最宏观的角度是在要求我们做什么。在这题中，就是一艘船要行驶到目的地，在中途会出现掉头的事件。

第二步，理清每个变量的含义。在这道题中，主要的变量有这些： S，v_{0}，v_{1}，t_{1}，v_{2}，t_{2}，n，T_{i}。有那么多变量，怎么快速的捕捉到它们并弄清它们的含义呢？这里教大家一个小技巧：在碰到题面较长的题目时，可以在做完第一步后，先看一看输入输出格式里涉及的变量，再继续细致地读题，着重关注这些变量的含义。 这样做的好处就是读题时不容易模模糊糊，更能快速理清题意。那么在这题中除了 n 以外的变量显然都需要我们着重地关注。读者现在可以自己带着这个思路回去再重新读一遍题目，看看效率会不会高一些？

第三步，理清各个变量之间的逻辑关系，在脑子里尝试简化题意。这一步做完，一道题的大意就能被你掌握了！

接下来就要解决这个题目了。由于船只有向前和向后两个方向，而且方向相同的一段时间内速度是相等的，而这两种状态的分界就是思念的起止时间——向前的时间就是每一次思念结束到下一次思念开始之间，向后的时间就是每次思念开始到这次思念结束。所以我们可以按照 T_{i} 来分段。先处理好思念的时间和速度，直接按题意写就可以了——第一次思念的时间和速度分别是 t_{1} 和 v_{1}，在每一次思念结束的时候让 t_{1}+=t_{2},v_{1}+=v_{2}，就能使得处理下一次思念时 t_{1} 就是时间， v_{1} 就是速度了。那么一次思念行驶的路程就是 v_{1}\times t_{1} 了。而对于向前行驶的路程，v_{0} 不会变，用 pret 来记录上一次思念结束的时间，nowt 来表示这一次思念开始的时间（事实上就是 T_{i}），那么向前的路程就是 (nowt-pret)\times v_{0} 了。只要用 dis 记录行驶的距离，处理每一段向前的时候看一看会不会抵达目的地，会的话直接输出就行了。这里注意，得到的时间应该是 pret+(D-dis)/v_{0}，还要记得向上取整。但是，可能最后所有思念完了后还没有到目的地，那就最后特判一下，或者直接加一个思念时间为 inf。

对于输出，就是按照 1min=60s，1 h=60min=3600s,1 day=24h=86400s 得到日，时，分，秒。这样题目就解决了，核心代码如下：

这是输出部分：

void print(int t){
    int day=(t/86400)+1;//因为是4月1日开始，所以日期要加一
    t%=86400;
    int hor=(t/3600);
    t%=3600;
    int m=t/60;
    t%=60;
    pf("202304%02dat%02d:%02d:%02d",day,hor,m,t); 
}

这是处理部分：

T[n+1]=2100000000;
while(1){
    nowt=T[++tmp];
    if(dis+(ll)(nowt-pret)*v>=S){//如果像我一样是增加一个inf的时间，要注意乘法可能超出int范围
        int extra=((S-dis)%v!=0);
        print((S-dis)/v+extra+pret);
        return 0;
    }
    dis+=(nowt-pret)*v;
    dis=max(0,dis-v1*t1);//如果掉头时到了家乡会停下
    pret=nowt+t1;
    v1+=v2,t1+=t2;
}

视频讲解