[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;
}