AtCoder｜Bus Stops

AtCoder题解｜ABC 319 E - Bus Stops

---

题目信息 📚

【题目描述】

Takahashi is initially at his house and is about to visit Aoki’s house.

There are $N$ bus stops numbered $1$ to $N$ between the two houses, and Takahashi can move between them in the following ways:

• He can walk from his house to bus stop $1$ in $X$ units of time.
• For each $i=1,2,\ldots,N-1$, a bus departs from bus stop $i$ at each time that is a multiple of $P_i$, and by taking this bus, he can get to bus stop $(i+1)$ in $T_i$ units of time. Here, the constraints guarantee that $1 \leq P_i \leq 8$.
• Takahashi can walk from bus stop $N$ to Aoki’s house in $Y$ units of time.

For each $i=1,2,\ldots,Q$, process the following query:

Find the earliest time that Takahashi can arrive at Aoki’s house when he leaves his house at time $q_i$.

Note that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.

【输入】

The input is given from Standard Input in the following format:

$N$ $X$ $Y$

$P_1$, $T_1$

$P_2$, $T_2$

$\vdots$

$P_{N-1}$, $T_{N-1}$

$Q$

$q_1$

$q_2$

$\vdots$

$q_Q$

【输出】

Print $Q$ lines. For each $i=1,2,\ldots,Q$, the $i$-th line should contain the answer to the $i$-th query.

【数据范围】

• $2 \leq N \leq 10^5$
• $1 \leq X, Y \leq 10^9$
• $1 \leq P_i \leq 8$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq q_i \leq 10^9$

All input values are integers.

【输入样例1】

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

【输出样例1】

34
22
710511052
136397548
763027402
644706946
447672250

For the first query, Takahashi can move as follows to arrive at Aoki’s house at time $34$.

• Leave his house at time $13$.
• Walk from his house and arrive at bus stop $1$ at time $15$.
• Take the bus departing from bus stop $1$ at time $15$ and arrive at bus stop $2$ at time $19$.
• Take the bus departing from bus stop $2$ at time $24$ and arrive at bus stop $3$ at time $30$.
• Take the bus departing from bus stop $3$ at time $30$ and arrive at bus stop $4$ at time $31$.
• Walk from bus stop $4$ and arrive at Aoki’s house at time $34$.

For the second query, Takahashi can move as follows and arrive at Aoki’s house at time $22$.

• Leave his house at time $0$.
• Walk from his house and arrive at bus stop $1$ at time $2$.
• Take the bus departing from bus stop $1$ at time $5$ and arrive at bus stop $2$ at time $9$.
• Take the bus departing from bus stop $2$ at time $12$ and arrive at bus stop $3$ at time $18$.
• Take the bus departing from bus stop $3$ at time $18$ and arrive at bus stop $4$ at time $19$.
• Walk from bus stop $4$ and arrive at Aoki’s house at time $22$.

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_e

---

题目解析 🍉

【题目分析】

模拟 + 暴力做法很容易想到，但是如何优化是个比较大的难题。

需要运用 数学 + 思维 的方法。（具体过程见下面代码）

官方题解传送门

https://atcoder.jp/contests/abc319/editorial/7141

https://atcoder.jp/contests/abc319/editorial/7122

【C++代码】

模拟 + 暴力（TLE） ❌

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, x, y, q, p[N], t[N], s, e;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入公交信息
    cin >> n >> x >> y;
    for (int i = 1; i <= n - 1; i++) {
        cin >> p[i] >> t[i];
    }

    // q次查询
    cin >> q;
    for (int i = 1; i <= q; i++) {
        // 模拟出发过程
        cin >> s;
        s += x; // 家到公交站1
        // 各个公交站点
        for (int j = 1; j <= n - 1; j++) {
            if (s % p[j])
                s = s + p[j] - s % p[j];
            s += t[j];
        }
        s += y;  // 公交站n到家
        cout << s << endl;
    }

    return 0;
}

优化法 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, x, y, q, p[N], t[N], s, e;
LL ans[1000];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入相关数据
    cin >> n >> x >> y;
    for (int i = 1; i <= n - 1; i++) {
        cin >> p[i] >> t[i];
    }

    // 预处理一个大循环（lcm(1, 2, 3,...8) = 840）
    // 840为最极端的情况，即pi取遍了1～8
    // 在一般测试样例中，lcm(p1, p2...pn-1)一般到不了840
    // 但是大循环840一定是小循环的倍数，所以直接处理大循环即可
    for (int i = 0; i < 840; i++) {
        LL cur = i;
        for (int j = 1; j <= n - 1; j++) {
            if (cur % p[j])
                cur = cur + p[j] - cur % p[j];
            cur += t[j];
        }
        ans[i] = cur - i;   // ans[i]表示时刻i到达第一个站点，后续到达第n个公交站点需要的时间
    }

    // q次查询，每次查询只需要获得到达第一个站点的时间s+x
    // 就可以通过预处理的ans数组，算出在(s+x)在大循环840中的位置
    // ans[(s+x)%840]即为公交上花费的总时间
    // 最后再加上y即可
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> s;
        s += x;
        cout << s + ans[s % 840] + y << endl;
    }

    return 0;
}

---

【Python代码】

模拟 + 暴力（TLE） ❌

# 输入公交站点信息
N, x, y = map(int, input().split())
p = [None] * (N - 1)
t = [None] * (N - 1)
for i in range(N - 1):
    p[i], t[i] = map(int, input().split())

# 输入查询次数
Q = int(input())

# Q次查询
for i in range(Q):
    # 模拟出发过程
    curtime = int(input()) # 输入出发时间
    curtime += x  # 家 → 站点1

    # N个站点
    for j in range(N - 1):
        if (curtime % p[j]):
            curtime += p[j] - curtime % p[j]
        curtime += t[j]

    curtime += y # 站点N → 终点
    print(curtime)

优化法 ✅