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 個酒店坐標(biāo)是 xi，現(xiàn)在有一個游客，他每天最多能走?L 步，而且必須在一天結(jié)束時住進(jìn)酒店，給出 Q 個詢問，每次給出?a、b 代表第 a 個酒店與第 b 個酒店，問從 a?到 b?最少花費(fèi)要幾天

思路：

上來就想到了二分，但二分的話時間復(fù)雜度仍然會超時

看別人用倍增處理狀態(tài)的做法，dp[i][j] 表示從 i 出發(fā)，經(jīng)過 1<<j 天所能達(dá)到的最遠(yuǎn)位置，也就是提前處理好 2^x 天數(shù)可到達(dá)的最遠(yuǎn)距離

先預(yù)處理 2^0 即第一天可到達(dá)的最遠(yuǎn)距離，即使用二分來查找可到達(dá)的最遠(yuǎn)距離

于是，就有狀態(tài)轉(zhuǎn)移方程：dp[i][j]=dp[dp[i][j-1]][j-1]，即第 i 個點(diǎn)的第 2^j 天的最遠(yuǎn)距離等于第 i 個點(diǎn)第 2^(j-1) 天到達(dá)的點(diǎn)的第 2^(j-1) 天的最遠(yuǎn)距離

簡單來說，即：2^j=2^(j-1)*2=2^(j-1)+2^(j-1)

最后求結(jié)果時，從后向前找到 a 可到達(dá)的最遠(yuǎn)小于等于 b?的某點(diǎn)距離，然后不斷的縮小求 x-b 的最短距離統(tǒng)計(jì)即可，需要注意的是，由于一開始預(yù)處理了第 1 天可到達(dá)的最遠(yuǎn)距離，因此最終結(jié)果要 +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++){//預(yù)處理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; }

?

總結(jié)

以上是生活随笔為你收集整理的高橋君とホテル / Tak and Hotels（AtCoder-2039）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。