题目地址：洛谷：【P1081】开车旅行 – 洛谷

题目描述

小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1 到 N 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为Hi，城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j] = |Hi− Hj|。 旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X 公里就结束旅行。小 A 和小 B的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。
在启程之前，小 A 想知道两个问题：

1. 对于一个给定的 X=X0，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2. 对任意给定的 X=Xi和出发城市 Si，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

输入输出格式

输入格式：
第一行包含一个整数 N，表示城市的数目。
第二行有 N 个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N 的海拔高度，即 H1，H2，……，Hn，且每个 Hi都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M，表示给定 M 组 Si和 Xi。
接下来的 M 行，每行包含 2 个整数 Si和 Xi，表示从城市 Si出发，最多行驶 Xi公里。

输出格式：
输出共 M+1 行。
第一行包含一个整数 S0，表示对于给定的 X0，从编号为 S0的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 Si和
Xi下小 A 行驶的里程总数和小 B 行驶的里程总数。

输入输出样例

输入样例#1：

4 
2 3 1 4 
3 
4 
1 3 
2 3 
3 3 
4 3

输出样例#1：

1 
1 1 
2 0 
0 0 
0 0 

输入样例#2：

10 
4 5 6 1 2 3 7 8 9 10 
7 
10 
1 7 
2 7 
3 7 
4 7 
5 7 
6 7 
7 7 
8 7 
9 7 
10 7

输出样例#2：

2 
3 2 
2 4 
2 1 
2 4 
5 1 
5 1 
2 1 
2 0 
0 0 
0 0

说明

对于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，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证Hi 互不相同。

题解

我们可以把距离加入一个set中，每次从set中二分找到当前处理的城市，从该城市的前驱，前驱的前驱，后继，后继的后继中找到两个最近的作为A和B的目标城市，组成一个链表，处理完一个城市就从set中删掉一个城市。然后在链表上二分，处理出nnxt[i][j]表示从i出发，两人各开了[eq]2^j[/eq]天后到达的城市，顺便求出disa[i][j]表示从i出发，两人各开了[eq]2^j[/eq]天，这段时间中A行驶的距离，以及disb[i][j]类似前面的定义。这个倍增列表可以通过常规的类似倍增LCA的方法求到。
对于第一个问题，枚举出发地利用上述预处理信息计算比值即可。
对于第二个问题，直接计算即可。
注意倍增终点最后一次是B开的，也就是说A可能还会继续往前开一次，这个要特判一下。
其实是个码农细节题，写起来挺烦的。思路上难度不太大。
复杂度上，预处理链表是O(N \log N)，预处理倍增数组是O(N \log N)，子问题1是O(N \log N)，子问题2是O(M \log N)。因此总复杂度还是O(N \log N)。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <set>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;
const double EPS = 1e-8;

struct Node {
    int hei, id;
    inline bool operator<(const Node &rhs) const {
        return hei < rhs.hei;
    }
};

std::set<Node> heis;
int n, hei[MAXN], nxt[MAXN][2], nnxt[MAXN][20], disa[MAXN][20], disb[MAXN][20], x0, m, si, xi;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        hei[i] = readint();
        heis.insert(Node {hei[i], i});
    }
    for(int i = 1; i <= n; i++) {
        auto it1 = heis.lower_bound(Node {hei[i], i}), it2 = it1;
        if(it1 != heis.end()) it1++; 
        if(it2 != heis.begin()) it2--;
        for(int j = 0; j < 2; it1++, j++) {
            if(it1 == heis.end()) break;
            if(!nxt[i][0]) {
                nxt[i][0] = it1->id;
            } else if(abs(hei[i] - it1->hei) < abs(hei[i] - hei[nxt[i][0]])
                || (abs(hei[i] - it1->hei) == abs(hei[i] - hei[nxt[i][0]]) 
                && it1->hei < hei[nxt[i][0]])) {
                nxt[i][1] = nxt[i][0];
                nxt[i][0] = it1->id;
            } else if(!nxt[i][1]) {
                nxt[i][1] = it1->id;
            } else if(abs(hei[i] - it1->hei) < abs(hei[i] - hei[nxt[i][1]])
                || (abs(hei[i] - it1->hei) == abs(hei[i] - hei[nxt[i][1]]) 
                && it1->hei < hei[nxt[i][1]])) {
                nxt[i][1] = it1->id;
            }
        }
        for(int j = 0; j < 2; it2--, j++) {
            if(it2->id == i && it2 == heis.begin()) break;
            if(!nxt[i][0]) {
                nxt[i][0] = it2->id;
            } else if(abs(hei[i] - it2->hei) < abs(hei[i] - hei[nxt[i][0]])
                || (abs(hei[i] - it2->hei) == abs(hei[i] - hei[nxt[i][0]]) 
                && it2->hei < hei[nxt[i][0]])) {
                nxt[i][1] = nxt[i][0];
                nxt[i][0] = it2->id;
            } else if(!nxt[i][1]) {
                nxt[i][1] = it2->id;
            } else if(abs(hei[i] - it2->hei) < abs(hei[i] - hei[nxt[i][1]])
                || (abs(hei[i] - it2->hei) == abs(hei[i] - hei[nxt[i][1]]) 
                && it2->hei < hei[nxt[i][1]])) {
                nxt[i][1] = it2->id;
            }
            if(it2 == heis.begin()) break;
        }
        heis.erase(Node {hei[i], i});
    }
    for(int i = 1; i <= n; i++) {
        nnxt[i][0] = nxt[nxt[i][1]][0];
        disa[i][0] = abs(hei[nxt[i][1]] - hei[i]);
        disb[i][0] = abs(hei[nnxt[i][0]] - hei[nxt[i][1]]);
    }
    for(int k = 1; k < 20; k++) {
        for(int i = 1; i <= n; i++) {
            nnxt[i][k] = nnxt[nnxt[i][k - 1]][k - 1];
            disa[i][k] = disa[i][k - 1] + disa[nnxt[i][k - 1]][k - 1];
            disb[i][k] = disb[i][k - 1] + disb[nnxt[i][k - 1]][k - 1];
        }
    }
    x0 = readint();
    double mn = INF * 2; int mnx = 0;
    for(int i = 1; i <= n; i++) {
        int da = 0, db = 0, p = i, d = 0;
        for(int k = 19; k >= 0; k--) {
            if(nnxt[p][k] && d + disa[p][k] + disb[p][k] <= x0) {
                d += disa[p][k] + disb[p][k];
                da += disa[p][k];
                db += disb[p][k];
                p = nnxt[p][k];
            }
        }
        if(nxt[p][1] && d + abs(hei[nxt[p][1]] - hei[p]) <= x0) {
            d += abs(hei[nxt[p][1]] - hei[p]);
            da += abs(hei[nxt[p][1]] - hei[p]);
            p = nxt[p][1];
        }
        double now = double(da) / db;
        if(db == 0) {
            if(mn - INF >= EPS) {
                mn = INF;
                mnx = i;
            } else if(fabs(mn - INF) < EPS && hei[i] > hei[mnx]) {
                mnx = i;
            }
        } else {
            if(mn - now >= EPS) {
                mn = now;
                mnx = i;
            } else if(fabs(mn - now) < EPS && hei[i] > hei[mnx]) {
                mnx = i;
            }
        }
    }
    printf("%d\n", mnx);
    m = readint();
    while(m--) {
        si = readint(); xi = readint();
        int p = si, d = 0, da = 0, db = 0;
        for(int k = 19; k >= 0; k--) {
            if(nnxt[p][k] && d + disa[p][k] + disb[p][k] <= xi) {
                d += disa[p][k] + disb[p][k];
                da += disa[p][k];
                db += disb[p][k];
                p = nnxt[p][k];
            }
        }
        if(nxt[p][1] && d + abs(hei[nxt[p][1]] - hei[p]) <= xi) {
            d += abs(hei[nxt[p][1]] - hei[p]);
            da += abs(hei[nxt[p][1]] - hei[p]);
            p = nxt[p][1];
        }
        printf("%d %d\n", da, db);
    }
    return 0;
}