题解 P1081 【开车旅行】

· · 题解

个人认为思维难度挺大的题QAQ

思路就是倍增， 然而预处理就挺麻烦的， 要用 离散化 加 双向链表 处理出每一个点A和B要到的下一个点。

这里的处理要用到一些技巧， 详见代码。

然后就是倍增：

f[i][j] 表示 从第i个点出发， A和B没人开了（1<<j）天所到的点， stA(B)表示 A(B) 的 路程。

因为A是先走的， 所以要看最后一步A还能不能再走一步。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m, l, r, j;
struct node{
    int i, v, l, r;
    bool operator < (const node & A) const{
        return v < A.v;
    }
}d[100005];
int h[100005], p[100005];
int stA[100005][21], stB[100005][21], f[100005][21];
int na[100005], nb[100005], a, b, ans = n;
double minn = 2147483647;
bool zuo(){
    if(!l) return 0;
    if(!r) return 1;
    return d[j].v-d[l].v<=d[r].v-d[j].v;
}
int pd(int a, int b){
    if(!a) return d[b].i;
    if(!b) return d[a].i;
    if(d[j].v-d[a].v <= d[b].v-d[j].v) return d[a].i;
    return d[b].i;
}
void make_st(){
    int i, j;
    for(j = 1; j <= 19; j++){
        for(i = 1; i <= n; i++){
            f[i][j] = f[f[i][j-1]][j-1];
            stA[i][j] = stA[i][j-1] + stA[f[i][j-1]][j-1];
            stB[i][j] = stB[i][j-1] + stB[f[i][j-1]][j-1];
        }
    }
}
void getab(long long x, int p){
    int i, j;
    a = b = 0;
    for(i = 19; i >= 0; i--){
        if(f[p][i] && (long long)(a + b + stA[p][i]+stB[p][i]) <= x){
            a += stA[p][i];
            b += stB[p][i];
            p = f[p][i];
        }
    }
    if(na[p] && a + b + stA[p][0] <= x) a += stA[p][0];
}
int main(){
    int i;
    long long x;
    scanf("%d", &n);
    for(i = 1; i <= n; i++) scanf("%d", &d[i].v);
    for(i = 1; i <= n; i++) d[i].i = i;
    sort(d+1, d+i);
    for(i = 1; i <= n; i++) p[d[i].i] = i;
    for(i = 1; i <= n; i++) d[i].l = i-1, d[i].r = i+1;
    d[1].l = d[n].r = 0;
    for(i = 1; i <= n; i++){
        j = p[i]; l = d[j].l; r = d[j].r;
        if(zuo()) nb[i] = d[l].i, na[i] = pd(d[l].l, r);//左边的近 
        else nb[i] = d[r].i, na[i] = pd(l, d[r].r);//右边的近 
        if(l) d[l].r = r;//用完j要把j删除掉  
        if(r) d[r].l = l;
    }
    for(i = 1; i <= n; i++){
        f[i][0] = nb[na[i]];
        stA[i][0] = abs(d[p[i]].v - d[p[na[i]]].v);
        stB[i][0] = abs(d[p[f[i][0]]].v - d[p[na[i]]].v);//记住结构体已经排序了， 所以要用他们的排名获取信息 
    }
    make_st();
    scanf("%lld%d", &x, &m);
    for(i = 1; i <= n; i++){
        getab(x, i);
        if(b && 1.0*a/b < minn){
            minn = 1.0*a/b;
            ans = i;
        }
    }
    printf("%d\n", ans);
    for(i = 1; i <= m; i++){
        scanf("%d%lld", &j, &x);
        getab(x, j);
        printf("%d %d\n", a, b);
    }
    return 0;
}