题目描述
小 (A) 和小 (B) 决定利用假期外出旅行，他们将想去的城市从 (1) 到 (N) 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 (i)的海拔高度为 (H_i)，城市 (i) 和城市 (j) 之间的距离 (d_{[i,j]}) ,([i,j])恰好是这两个城市海拔高度之差的绝对值，即 (d_{[i,j]}=|H_i-H_j|)。
旅行过程中，小 (A) 和小 (B) 轮流开车，第一天小 (A) 开车，之后每天轮换一次。他们计划选择一个城市 (S) 作为起点，一直向东行驶，并且最多行驶 (X) 公里就结束旅行。小 (A) 和小 (B) 的驾驶风格不同，小 (B) 总是沿着前进方向选择一个最近的城市作为目的地，而小(A)总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 (X) 公里，他们就会结束旅行。
在启程之前，小 (A) 想知道两个问题：
对于一个给定的 (X=X_0),从哪一个城市出发，小 (A) 开车行驶的路程总数与小 (B) 行驶的路程总数的比值最小（如果小 (B) 的行驶路程为 (0) ，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 (A) 开车行驶的路程总数与小 (B) 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
对任意给定的 (X=X_i) 和出发城市 (S_i) ,小 (A) 开车行驶的路程总数以及小 (B) 行驶的路程总数。
输入输出格式
输入格式
第一行包含一个整数 (N) ，表示城市的数目。
第二行有 (N) 个整数，每两个整数之间用一个空格隔开，依次表示城市 (1) 到城市 (N) 的海拔高度，即 (H_1),(H_2),(…),(H_n) ,且每个 (H_i) 都是不同的。
第三行包含一个整数 (X_0)。
第四行为一个整数 (M) ，表示给定 (M) 组 (S_i)和 (X_i) 。
接下来的 (M) 行，每行包含 (2) 个整数 (S_i) 和 (X_i), 表示从城市 (S_i) 出发，最多行驶 (X_i) 公里。
输出格式
输出共 (M+1) 行。
第一行包含一个整数 (S_0)，表示对于给定的 (X_0),从编号为 (S_0) 的城市出发，小 (A) 开车行驶的路程总数与小 (B) 行驶的路程总数的比值最小。
接下来的 (M) 行，每行包含 (2) 个整数，之间用一个空格隔开，依次表示在给定的 (S_i) 和 (X_i) 下小 (A) 行驶的里程总数和小 (B) 行驶的里程总数。
数据范围与约定
对于30%的数据，有 (1≤N≤20),(1≤M≤20) ;
对于40%的数据，有 (1≤N≤100),(1≤M≤100)；
对于50%的数据，有 (1≤N≤100),(1≤M≤1,000)；
对于70%的数据，有 (1≤N≤1,000),(1≤M≤10,000) ;
对于100%的数据，有 (1≤N≤100,000),(1≤M≤100,000), (-10^9≤H_i≤10^9) ,数据保证 (H_i) 互不相同。
题解
我们先来看前70%的数据，我们发现可以用 (O(n^2)) 的预处理来算出小(A)在某个位置i的下一个位置和小(B)在某个位置的下一个位置。然后对于第一个问题我们可以枚举每一个出发点，然后进行比较，对于第二问我们可以直接模拟计算即可。
我们再来考虑100%的算法，我们可以发现上面这个算法最最耗时的地方一个是在预处理上，一个是在枚举和模拟上。
我们依次来考虑是否可以优化：
1.对于 (O(n^2)) 的预处理时，我们可以利用数据结构来优化使其降至 (O(nlogn)) ,我们需要一个支持插入操作和求区间第K大的数据结构，通常我们会用线段树、双向链、set、平衡树来维护，蒟蒻我对于其他几种不是很了解，只能用set来水了。注意在用set时迭代器是否越界。
2.对于枚举算法，我么发现我们找不出什么好的优化算法，所以我们只能放弃。
3.对于模拟，我们发现，是小(A)和小(B)轮流进行，我们可以考虑用倍增进行优化就像树上倍增求LCA一样，我们把小(A)和小(B)各走一步看作是一轮，记录(f[i][j])表示从(i)出发经过(2^j)轮后他们回到达的地方，记录(fa[i][j])表示从(i)出发，经过(2^j)轮后小(A)走过的路程，同理记录小(B)的为(fb[i][j])。
由于(2^{j-1} + 2^{j-1} = 2^j) ,考虑一下状态的转移：
(f[i][j] = f[f[i][j-1]][j-1]);
(fa[i][j] = fa[i][j-1] + fa[f[i][j-1]][j-1]);
(fb[i][j] = fb[i][j-1] + fb[f[i][j-1]][j-1]);
值得注意的是：
1.要考虑初始条件；
2.在进行倍增的过程中，如果无法两个人都走的时候注意考虑小(A)是否可以单独多走一步；
3.在递推过程中，我们考虑一下状态的产生顺序，发现要以j所在的维度为阶段。
代码
#include<bits/stdc++.h>
using namespace std;
int n, m, S, X;
long long h[100005];
int a[100005], b[100005];
struct Node{
long long val;
int pos;
bool friend operator < (const Node & x, const Node & y)
{
return x.val < y.val;
}
};
inline Node make_Node(int x, int y)
{
Node aa;
aa.val = x, aa.pos = y;
return aa;
}
set <Node> Set;
Node dis[5];
inline bool comp(const Node & x, const Node & y)
{
if(abs(x.val) == abs(y.val)) return x.val < y.val;
return abs(x.val) < abs(y.val);
}
void init1()
{
set <Node> :: iterator it;
for(int i = n; i > 0; -- i)
{
memset(dis, 0, sizeof(dis));
int cnt = 0;
Set.insert(make_Node(h[i], i));
it = Set.find(make_Node(h[i], i));
if(it != Set.begin())
{
-- it, dis[++ cnt] = *it;
if(it != Set.begin()) --it, dis[++ cnt] = *it, ++ it;
++ it;
}
++ it;
if(it != Set.end())
{
dis[++ cnt] = *it, ++ it;
if(it != Set.end()) dis[++ cnt] = *it;
}
for(int j = 1; j <= cnt; ++ j) dis[j].val -= h[i];
sort(dis + 1, dis + cnt + 1, comp);
a[i] = dis[2].pos, b[i] = dis[1].pos;
}
return;
}
int f[100005][20];
long long fa[100005][20], fb[100005][20];
int t;
void init2()
{
t = (int) log(n) / log(2) + 1;
for(int i = 1; i <= n; ++ i)
{
int posa = a[i], posb = b[a[i]];
f[i][0] = posb, fa[i][0] = posa ? abs(h[i] - h[posa]) : 0, fb[i][0] = posb ? abs(h[posa] - h[posb]) : 0;
}
for(int j = 1; j <= t; ++ j)
for(int i = 1; i <= n; ++ i)
f[i][j] = f[f[i][j - 1]][j - 1], fa[i][j] = fa[i][j - 1] + fa[f[i][j - 1]][j - 1], fb[i][j] = fb[i][j - 1] + fb[f[i][j - 1]][j - 1];
}
void Get_ans(int s, int x0, long long & suma, long long &sumb)
{
suma = sumb = 0;
for(int i = t; i >= 0; -- i)
if(f[s][i] && fa[s][i] + fb[s][i] <= x0)
{
suma += fa[s][i], sumb += fb[s][i], x0 -= (fa[s][i] + fb[s][i]);
s = f[s][i];
}
int posa = a[s];
if(!posa) return;
if(abs(h[posa] - h[s]) <= x0) suma += abs(h[posa] - h[s]);
return;
}
int main()
{
// freopen("drive.in", "r", stdin);
// freopen("drive.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) scanf("%lld", &h[i]);
init1();
// for(int i = 1; i <= n; ++ i) printf("%d %d
", a[i], b[i]);
init2();
scanf("%d", &X);
long long ansa = 0x7fffffff, ansb = 1;
long long suma, sumb;
for(int i = 1; i <= n; ++ i)
{
Get_ans(i, X, suma, sumb);
if(sumb == 0) continue;
if(ansa * sumb > suma * ansb) ansa = suma, ansb = sumb, S = i;
}
printf("%d
", S);
scanf("%d", &m);
for(int i = 1; i <= m; ++ i)
{
scanf("%d%d", &S, &X);
Get_ans(S, X, suma, sumb);
printf("%lld %lld
", suma, sumb);
}
return 0;
}