[NOIP2012提高]开车旅行 题解
![[NOIP2012提高]开车旅行 题解](https://ksmeow.moe/wp-content/uploads/2018/05/180504b.jpg "180504b")
题目地址：洛谷：【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 想知道两个问题：
- 对于一个给定的 X=X0，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
- 对任意给定的 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;
}
