6463: Tak and Hotels II(倍增)

题目描述
N hotels are located on a straight line. The coordinate of the i-th hotel (1≤i≤N) is xi.
Tak the traveler has the following two personal principles:
He never travels a distance of more than L in a single day.
He never sleeps in the open. That is, he must stay at a hotel at the end of a day.
You are given Q queries. The j-th (1≤j≤Q) query is described by two distinct integers aj and bj. For each query, find the minimum number of days that Tak needs to travel from the aj-th hotel to the bj-th hotel following his principles. It is guaranteed that he can always travel from the aj-th hotel to the bj-th hotel, in any given input.

Constraints
2≤N≤105
1≤L≤109
1≤Q≤105
1≤xi<x2<…<xN≤109
xi+1−xi≤L
1≤aj,bj≤N
aj≠bj
N,L,Q,xi,aj,bj are integers.
Partial Score
200 points will be awarded for passing the test set satisfying N≤103 and Q≤103.
输入
The input is given from Standard Input in the following format:
N
x1 x2 … xN
L
Q
a1 b1
a2 b2
:
aQ bQ
输出
Print Q lines. The j-th line (1≤j≤Q) should contain the minimum number of days that Tak needs to travel from the aj-th hotel to the bj-th hotel.
样例输入

9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5

样例输出

4 2 1 2

提示
For the 1-st query, he can travel from the 1-st hotel to the 8-th hotel in 4 days, as follows:
Day 1: Travel from the 1-st hotel to the 2-nd hotel. The distance traveled is 2.
Day 2: Travel from the 2-nd hotel to the 4-th hotel. The distance traveled is 10.
Day 3: Travel from the 4-th hotel to the 7-th hotel. The distance traveled is 6.

Day 4: Travel from the 7-th hotel to the 8-th hotel. The distance traveled is 10.

题意：给你直线上一些点的坐标，一天最大的移动距离，要求每天结束时必须在一个点上。1e5次询问，每次询问从第a个点到第b个点最少要几天。

解题思路：

dp[x][y]表示第x个点2^y次方的天数能到的最远点。暴力或二分预处理dp[x][0]，然后 dp[x][i] = dp[f[x][i-1]][i-1]；
查询的时候, 找到从cur（当前点）出发的第一个小于b位置的dp[cur][j]，最后答案加上1（2^0）

//dp[x][y]表示第x个点2^ y次方的天数能到的最远点。
$dp[j][i]=dp[dp[j][i-1]][i-1];$
// 含义以i等于1为例，意义是第j个点2天能到的最远点。那么这不就是我一天最远能走到的点，的一天能走到的最远的点嘛
//其余的就可以依次类推

代码：

int main() {while (cin >>n) {for (int i = 1; i <= n; ++i)cin >> a[i];cin >> L >> Q;for (int i = 1; i <= n; ++i) {//upper_bound()是找到第一个大于的位置，-a得到下标，再减1得到最后一个小于等于的点int id = upper_bound(a + 1, a + 1 + n, a[i] + L)-a-1;if (a[i] + L >= a[n]) //如果可以一次过那么在一天内就可以直接到n点了dp[i][0] = n;elsedp[i][0] = id;}for (int i = 1; i <= 30; ++i)for (int j = 1; j <= n; ++j)dp[j][i] = dp[dp[j][i - 1]][i - 1];while (Q--) {cin >> x >> y;if (x > y) swap(x, y);ans = 0;//从大到小枚举for (int i = 30; i >= 0; --i) {if (dp[x][i] < y) //从第一个点走的2^i的天数如果小于y，那么这个天数对于x点最优{ans += (1) << i;x = dp[x][i]; //如果还没到终点以这个点来找} }cout << ans+1 << endl;} }return 0; }

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

总结

以上是生活随笔为你收集整理的6463: Tak and Hotels II(倍增)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。