「NOIP 2012」开车旅行

Posted on | In

题目大意：一维坐标系上有 $N$ 个城市，每个城市的海拔互不相同，定义两城市间的距离为它们的海拔之差，如果存在两个城市与当前城市的海拔之差相同，则规定海拔较小的城市更近。小 $A$ 与小 $B$ 计划选择一个城市 $S$ 作为起点，然后一直向东行驶，第一天小 $A$ 开车，之后每天轮换一次。每一天他们都会从当前城市到达下一个目的地。小 $B$ 总是沿着前进方向选择一个最近的城市作为目的地，而小 $A$ 总是沿着前进方向选择第二近的城市作为目的地。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $X$ 公里，他们就会结束旅行。请你回答下面两个问题：

  1. 对于给定的 $X_0$，从哪一个城市出发，小 $A$ 开车行驶的路程总数与小 $B$ 行驶的路程总数的比值最小？
  2. 对于给定的 $S_i,X_i$，小 $A$ 行驶的里程总数和小 $B$ 行驶的里程总数各是多少？ （$i=1 \cdots M$）

$1 \leq N,M \leq 100000$

预处理距每个点第一第二近的城市可以用平衡树，考虑到只是查询前驱和后继，可以使用 $multiset$。

发现每 $2^i\ (i>0)$ 天结束后，都是再由小 $A$ 出发，然后就可以愉快地倍增了٩(๑>◡<๑)۶

#include <cstdio>
#include <algorithm>
#include <set>

const int N = 100005, INF = 0x3f3f3f3f;
int h[N], f[N][20], tmp1[N], tmp2[N], a[N][20], b[N][20];

struct Node1 {
    int h, id;
    bool operator < (const Node1 &rhs) const {
        return h < rhs.h;
    }
};
struct Node2 {
    int h1, h2, id;
    bool operator < (const Node2 &rhs) const {
        if (h1 == rhs.h1) return h2 < rhs.h2;
        return h1 < rhs.h1;
    }
} c[10];
std::multiset<Node1> S;
std::multiset<Node1>::iterator it;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int abs(int x) {
    return x > 0 ? x : -x;
}
void jump(int s, int x, int &aa, int &bb) {
    for (int i = 17; i >= 1; --i) {
        if (!a[s][i] || !b[s][i] || aa + bb + a[s][i] + b[s][i] > x) continue;
        aa += a[s][i], bb += b[s][i], s = f[s][i];
    }
    if (a[s][0] && aa + bb + a[s][0] <= x) aa += a[s][0];
}

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) h[i] = read();
    S.insert((Node1){-INF, 0}), S.insert((Node1){INF, 0});
    for (int i = n; i >= 1; --i) {
        it = S.lower_bound((Node1){h[i], i});
        c[0].id = 0;
        if (it->h < INF) {
            c[++c[0].id] = (Node2){abs(h[i]-it->h), it->h, it->id};
            if ((++it)->h < INF)
                c[++c[0].id] = (Node2){abs(h[i]-it->h), it->h, it->id};
            --it;
        }
        if ((--it)->h > -INF) {
            c[++c[0].id] = (Node2){abs(h[i]-it->h), it->h, it->id};
            if ((--it)->h > -INF)
                c[++c[0].id] = (Node2){abs(h[i]-it->h), it->h, it->id};
        }
        std::sort(c + 1, c + c[0].id + 1);
        if (c[0].id >= 1) tmp1[i] = c[1].id, tmp2[i] = c[1].h1;
        if (c[0].id >= 2) f[i][0] = c[2].id, a[i][0] = a[i][1] = c[2].h1;
        S.insert((Node1){h[i], i});
    }
    for (int i = 1; i <= n; ++i)
        f[i][1] = tmp1[f[i][0]], b[i][1] = tmp2[f[i][0]];
    for (int j = 2; j <= 17; ++j)
        for (int i = 1; i <= n; ++i) {
            f[i][j] = f[f[i][j-1]][j-1];
            if (f[i][j]) {
                a[i][j] = a[i][j-1] + a[f[i][j-1]][j-1];
                b[i][j] = b[i][j-1] + b[f[i][j-1]][j-1];
            }
        }
    int x = read(), s = 0, aa, bb;
    double ratio = INF;
    for (int i = 1; i <= n; ++i) {
        aa = bb = 0;
        jump(i, x, aa, bb);
        if (bb && aa * 1.0 / bb < ratio)
            ratio = aa * 1.0 / bb, s = i;
    }
    printf("%d\n", s);
    int m = read();
    while (m--) {
        s = read(), x = read();
        aa = bb = 0;
        jump(s, x, aa, bb);
        printf("%d %d\n", aa, bb);
    }
    return 0;
}