[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