[ARC060E] Tak and Hotels 题解

题目链接：[ARC060E] Tak and Hotels

题意：

一条笔直的公路上有 $N$ 个旅店，第 $i$ 个旅店的坐标是 $x_i$
高桥君旅行时有如下习惯：

• 他一天最多行走长度不大于 $L$ 的路程
• 他一定会选择一家旅店作为自己一天行程的终点

现在他有 $Q$ 组行程计划，对于每一组计划，他会从 旅店a 旅行到 旅店b $(a \neq b)$ 。你现在需要帮助他，求出每一组计划所需的最小天数

数据范围：

$2 \leq N \leq 10^5, 1 \leq L \leq 10^9, 1 \leq Q \leq 10^5$

$1 \leq x_1<x_2<\cdots<x_N \leq 10^9,~x_{i+1}-x_i \leq L$

题解标签写的倍增，结果进来是板子题。。

考虑倍增。设 $f(i,j)$ 表示从第 $i$ 个点出发，走 $2^j$ 步能到达的最远的节点，转移如下：

$$f(i, j)=f(f(i, j-1), j-1)$$

询问的时候，我们倒序枚举 $j$ ，至多枚举 $\mathcal{O}(\log n)$ 次

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define M ((int)(20))

int n,m,L,a[N],f[N][M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    a[n + 1] = 2 * INF; cin >> L;
    for(int i = 1; i <= n; i++) f[i][0] = upper_bound(a + 1, a + 2 + n, a[i] + L) - a - 1;
    for(int j = 1; j < M; j++)
        for(int i = 1; i <= n; i++) f[i][j] = f[f[i][j - 1]][j - 1];
    cin >> m;
    for(int s,t,x1 = 0, x2 = INF; m--; x1 = 0, x2 = INF)
    {
        cin >> s >> t; if(s > t) swap(s, t);
        for(int j = M - 1; ~j; j--) if(f[s][j] < t) {
            s = f[s][j]; down(x2, x1 + (1 << (j + 1))); x1 += (1 << j);
        }
        cout << min(x1 + 1, x2) << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/706523/solution-at-arc060-c