题解 AT3849 【[ABC084C] Special Trains】

题目大意

总共有 NN 个车站,每两个相邻的车站有单向的车.

从第 ii 个站到第 i+1i+1 个站 需要时间 CiC_i 分钟,且第一趟车在 SiS_i分钟时发(之后每隔 FiF_i 分钟发一辆车)。

并且 数据保证 FiF_i 能被 FiF_i 整除。

要你求出每以个点到 NN 的最少时间。

思路

因为 NN << 500500,所以不用多考虑,可以直接暴力模拟。

只要枚举出每一个点到其他各个点所需要最少的的时间即可。

但是虽然是需要求出 11~NNNN 的时间,但是事实上 NNNN 的时间为 00,无需考虑。

最后输出最少所需的时间(即算出数的和)即可。

核心代码

ans=max(ans,s[j]);
if(ans%f[j]!=0) ans=ans+f[j]-ans%f[j];/*此处指处于间隔的时间之内(即未发车)*/
ans+=c[j];/*加上所需时间*/
赞赏