[ABC319E] Bus Stops 题解
[ABC319E] Bus Stops 题解
题意简介
给定 \(n\) 个公交站。对于第 \(i\) 个公交站，在时刻 \(p_i \times k,k \in \mathbb{N}\) 有一辆公交车出发，在经过 \(t_i\) 的时间后，到达第 \(i+1\) 个公交站。
在走到第一个公交车之前需要走 \(X\) 时刻，做到最后一个公交站之后下车以后还需要走 \(Y\) 时刻。
约束：\(1 \le p_i \le 8\)
给定 \(m\) 次询问，每次询问给定出发时间 \(q_i\)，问所需要花费的最小时间。就是 \(q_i + X + \text{坐公交车花费时间} + Y\)。
题目分析
考虑到 \(1 \le p_i \le 8\)，这里有个小技巧：我们考虑（1~8）最小公倍数 840 时间范围内的时刻就够了。
如果 \(p_i\) 中出现了全部 1~8，那么经过 840 时刻之后，所有车站发车的“小周期”就可以“耦合”成大周期。如果不全部出现 1~8，那么 840 一定包含了其大周期。
我们考虑 \(f_i\) 表示在第 \(i\) 个时刻到达第 1 个车站情况下，坐到最后一个车站所需要花费的时间。我们贪心地一站一站往前坐车即可。
我们对于 840 个时刻全部预处理一遍，时间复杂度 \(O(\text{lcm}(p_i)\times n)\)。对于每个询问，我们可以除掉周期，用余数代入 \(f_i\)，\(O(1)\) 地得到答案，时间复杂度 \(O(m)\)。总时间复杂度 \(O(\text{lcm}(p_i)\times n + m)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const LL P = 840;
LL n,p[N],t[N],x,y;
LL f[P+5];
void init()
{
for(int i = 0;i < P;i++)
{
f[i] = i;
for(int j = 1;j <= n-1;j++)
{
if(f[i]%p[j] == 0)
{
f[i] += t[j];
}
else
{
f[i] = t[j] + (((f[i]-1)/p[j])+1)*p[j];
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> x >> y;
for(int i = 1;i <= n-1;i++)
{
cin >> p[i] >> t[i];
}
init();
LL ques = 0;
cin >> ques;
while(ques--)
{
LL q;
cin >> q;
q += x;
cout << (LL)(q/P*P + f[q%P] + y) << "\n";
}
return 0;
}