题目

到处都有

闲话

碰巧考场上出了 \(Noip\) 原题

然后这题自然而然想到

预处理一个点开始分别由 \(A，B\) 驾驶会走到的下一个点

然后用预处理的数组求答案

当然你会发现 \(X=X0\) 这一问和后面的问的解法没什么区别

这都不是重点

\(ccf\) 很良心给暴力 \(70\) 分

然后 \(100\) 分码得非常开心

解法一

没错，就是按闲话的思路

求下一个点 \(O(n^2)\) 可以做到，往后扫一遍依题算即可

然后对于每个询问暴力一步一步走知道无路可走

竟然给 \(70\) !

\(Code\)

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 1e5 + 5;
int n, m, h[N], nxt[N][2];
struct node{int a, b;};

void getNext()
{
    h[0] = 0x3f3f3f3f;
    for(register int i = 1; i <= n; i++)
    {
        int k1 = 0, k2 = 0;
        for(register int j = i + 1; j <= n; j++)
        {
            int z = abs(h[i] - h[j]);
            if (z < abs(h[i] - h[k1]) || (z == abs(h[i] - h[k1]) && h[j] < h[k1])) k2 = k1, k1 = j;
            else if (z == abs(h[i] - h[k1]) || z < abs(h[i] - h[k2]) || (z == abs(h[i] - h[k2]) && h[j] < h[k2])) k2 = j;
        }
        nxt[i][1] = k1, nxt[i][0] = k2;
    }
}

inline node solve(int S, int X)
{
    int p = 0, x = 0;
    node ret = {0, 0};
    while (nxt[S][p] != 0 && x + abs(h[S] - h[nxt[S][p]]) <= X)
    {
        if (!p) ret.a += abs(h[S] - h[nxt[S][p]]);
        else ret.b += abs(h[S] - h[nxt[S][p]]);
        x += abs(h[S] - h[nxt[S][p]]), S = nxt[S][p], p ^= 1;
    }
    return ret;
}

inline double calc(int x, int y)
{
    if (!y) return 0x3f3f3f3f;
    return 1.0 * x / y;
}

int main()
{
    scanf("%d", &n);
    for(register int i = 1; i <= n; i++) scanf("%d", &h[i]);
    getNext();
    LL S, X;
    scanf("%d", &X);
    int k = 0; double ans = 0x3f3f3f3f;
    for(register int i = 1; i <= n; i++)
    {
        node t = solve(i, X);
        if (calc(t.a, t.b) < ans || (calc(t.a, t.b) == ans && h[i] > h[k]))
            ans = calc(t.a, t.b), k = i;
    }
    printf("%d\n", k);
    scanf("%d", &m);
    for(; m; m--)
    {
        scanf("%lld%lld", &S, &X);
        node t = solve(S, X);
        printf("%d %d\n", t.a, t.b);
    }
}

解法二

没错，就是按照解法一的思路

首先我们发现一步一步跳太低效

也太给人灵感

一步一步跳？好熟悉？！

那就倍增啊

\(2\) 的幂次跳就是快！！

然后这不是最关键的地方

因为预处理还卡在 \(O(n^2)\)

相当于什么都没干

所以我们总得干点什么

是的

预处理实际上非常好玩

你可以用排序+链表非常常规地搞出来

当然，你可以更常规用平衡树来搞搞

我选择了后者（当然不可能手打平衡树，\(set\) 就是好）

这东西比较繁琐，要慢慢讨论

收获

用 \(set\) 如果涉及多个关键字怎么办？

这样定义

#include<set>
using namespace std;

struct nod{int h, id;};
struct cmp{bool operator()(const nod &a, const nod &b){return a.h < b.h;}};
set<nod, cmp> s;

于是我们申明了一个节点为 \(nod\) 类型的平衡树

那么各类使用参数也相应的改变

你会发现 \(h\) 是第一关键字

那它在比较时会先比较第一关键字，再比较第二关键字

学会了！

哦，\(AC\) 代码记录一波

#include<cstdio>
#include<algorithm>
#include<set>
#define LL long long
using namespace std;

const int N = 1e5 + 5;
int n, m, h[N], nxt[N][2];
LL F[N][20], A[N][20], B[N][20];
struct node{LL a, b;};
struct nod{int h, id;};
struct cmp{bool operator()(const nod &a, const nod &b){return a.h < b.h;}};
set<nod, cmp> tr;
set<nod, cmp>::iterator it, itt;

inline void swap(nod &x, nod &y){nod t; t = x, x = y, y = t;}

void getNext()
{
    tr.insert(nod{h[n], n});
    for(register int i = n - 1; i; i--)
    {
        nod k1 = {0x3f3f3f3f, 0}, k2 = {0x3f3f3f3f, 0};
        it = tr.lower_bound(nod{h[i], i});
        if (it == tr.begin())
        {
            k1 = *it;
            if (++it != tr.end()) k2 = *it;
        }
        else if (it == tr.end())
        {
            k1 = *(--it);
            if (it != tr.begin()) k2 = *(--it);
        }
        else{
            itt = it, --it;
            int count = 0; nod l = *it, r = *itt;
            while (1)
            {
                if (abs(h[i] - l.h) < abs(h[i] - r.h) || (abs(h[i] - l.h) == abs(h[i] - r.h) && l.h < r.h))
                {
                    if (!count)
                    {
                        k1 = l, ++count;
                        if (it == tr.begin()){l = {0x3f3f3f3f, 0}; continue;}
                        l = *(--it);
                    }
                    else{k2 = l; break;}
                }
                else{
                    if (!count)
                    {
                        k1 = r, ++count, r = *(++itt);
                        if (itt == tr.end()) r = {0x3f3f3f3f, 0};
                    }
                    else{k2 = r; break;}
                }
            }
        }
        if (abs(h[i] - k1.h) > abs(h[i] - k2.h) || (abs(h[i] - k1.h) == abs(h[i] - k2.h) && k1.h > k2.h)) swap(k1, k2);
        nxt[i][1] = k1.id, nxt[i][0] = k2.id;
        tr.insert(nod{h[i], i});
    }
}

void getF()
{
    for(register int i = 1; i <= n; i++)
        F[i][0] = nxt[nxt[i][0]][1],
        A[i][0] = abs(h[i] - h[nxt[i][0]]),
        B[i][0] = abs(h[nxt[i][0]] - h[nxt[nxt[i][0]][1]]);
    for(register int j = 1; j <= 17; j++)
    for(register int i = 1; i <= n; i++)
        F[i][j] = F[F[i][j - 1]][j - 1],
        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];
}

inline node solve(int S, LL X)
{
    int p = 0; LL x = 0;
    node ret = {0, 0};
    for(register int i = 17; i >= 0; i--)
    if (F[S][i] && x + A[S][i] + B[S][i] <= X)
    {
        ret.a += A[S][i], ret.b += B[S][i];
        x += A[S][i] + B[S][i], S = F[S][i];
    }
    while (nxt[S][p] && x + abs(h[S] - h[nxt[S][p]]) <= X)
    {
        if (!p) ret.a += abs(h[S] - h[nxt[S][p]]);
        else ret.b += abs(h[S] - h[nxt[S][p]]);
        x += abs(h[S] - h[nxt[S][p]]), S = nxt[S][p], p ^= 1;
    }
    return ret;
}

inline double calc(int x, int y)
{
    if (!y) return 0x3f3f3f3f;
    return 1.0 * x / y;
}

int main()
{
    scanf("%d", &n);
    for(register int i = 1; i <= n; i++) scanf("%d", &h[i]);
    getNext(), getF();
    int S; LL X;
    scanf("%lld", &X);
    int k = 0; double ans = 0x3f3f3f3f;
    for(register int i = 1; i <= n; i++)
    {
        node t = solve(i, X);
        if (calc(t.a, t.b) < ans || (calc(t.a, t.b) == ans && h[i] > h[k]))
            ans = calc(t.a, t.b), k = i;
    }
    printf("%d\n", k);
    scanf("%d", &m);
    for(; m; m--)
    {
        scanf("%d%lld", &S, &X);
        node t = solve(S, X);
        printf("%lld %lld\n", t.a, t.b);
    }
}