Problem Description

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.

Input

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

N
x1 x2 … xN
L
Q
a1 b1
a2 b2
:
aQ bQ

Output

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.

Example

Sample Input 1

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

Sample Output 1

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.

题意：n 个酒店在一条直线上，第 i 个酒店坐标是 xi，现在有一个游客，他每天最多能走 L 步，而且必须在一天结束时住进酒店，给出 Q 个询问，每次给出 a、b 代表第 a 个酒店与第 b 个酒店，问从 a 到 b 最少花费要几天

思路：

上来就想到了二分，但二分的话时间复杂度仍然会超时

看别人用倍增处理状态的做法，dp[i][j] 表示从 i 出发，经过 1<<j 天所能达到的最远位置，也就是提前处理好 2^x 天数可到达的最远距离

先预处理 2^0 即第一天可到达的最远距离，即使用二分来查找可到达的最远距离

于是，就有状态转移方程：dp[i][j]=dp[dp[i][j-1]][j-1]，即第 i 个点的第 2^j 天的最远距离等于第 i 个点第 2^(j-1) 天到达的点的第 2^(j-1) 天的最远距离

简单来说，即：2^j=2^(j-1)*2=2^(j-1)+2^(j-1)

最后求结果时，从后向前找到 a 可到达的最远小于等于 b 的某点距离，然后不断的缩小求 x-b 的最短距离统计即可，需要注意的是，由于一开始预处理了第 1 天可到达的最远距离，因此最终结果要 +1

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;int x[N]; int dp[N][50]; int main(){int n;scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&x[i]);int L,Q;scanf("%d%d",&L,&Q);for(int i=1; i<=n ;i++){//预处理dp[i][0]int left=i+1,right=n;while(left<=right){int mid=(left+right)/2;if(x[mid]<=L+x[i])left=mid+1;elseright=mid-1;}if(x[i]+L>=x[n])dp[i][0]=n;elsedp[i][0]=left-1;}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--){int a,b;scanf("%d%d",&a,&b);if(b<a)swap(a,b);LL res=0;for(int i=30; i>=0; i--){if(dp[a][i]<b){res+=(1<<i);a=dp[a][i];}}printf("%lld\n",res+1);}return 0; }

 

总结

以上是生活随笔为你收集整理的高橋君とホテル / Tak and Hotels（AtCoder-2039）的全部内容，希望文章能够帮你解决所遇到的问题。

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