RenaMoe's Blog

念念不忘，必有回响

0%

题解 P1081 开车旅行

发表于 分类于 ， Valine：

题面

题面不好概括，贴个链接好了。

你一个倍增题怎么这么难码啊！抱歉，是我的亲手写的 sb bug 让我调一天。

还是放一下题面好了：

思路

调完已经筋疲力尽了，不多说。

找距离最近的，那就倒着插入 set 来维护。

利用倍增的思想，预处理 \(nxt_{i,j}\) 表示 i 点走 \(2^j\) 次到达位置，同理 \(fa_{i,j},fb_{i,j}\) 为两人答案。

细节看代码好了。

代码

得 long long，这里 define 是我偷懒了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <set>
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

namespace RenaMoe {

#define int long long

template <typename TT> inline void read(TT &x) {
    x = 0; bool f = false; char in = getchar();
    while (!isdigit(in)) { if (in == '-') f = true; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x = f ? -x : x;
}

const int N = 1e5 + 9;
const int INF = 1e18;

struct City {
    int h, id;
    City() {}
    City(int _h, int _id) : h(_h), id(_id) {}
    bool operator <(const City &t) const {
        return h == t.h ? id < t.id : h < t.h; 
    }
};
struct Tmp {
    int h, dth, id;// dth 为距离（delta h）
    Tmp() {}
    Tmp(City t) : h(t.h), id(t.id) {}
    bool operator <(const Tmp &t) const {
        return dth == t.dth ? h < t.h : dth < t.dth;// 一定要好好读题qwq
    }
};

int n, m, ans_a, ans_b;
int h[N], nxt[N][20], fa[N][20], fb[N][20], da[N], db[N], na[N], nb[N];
multiset<City> st;
Tmp tmp[5];

inline void solve(int s, int d) {
    ans_a = ans_b = 0;
    for (int i = 19; ~i; --i)
        if (nxt[s][i] && ans_a + ans_b + fa[s][i] + fb[s][i] <= d) {
            ans_a += fa[s][i];
            ans_b += fb[s][i];
            s = nxt[s][i];
        }
}

inline void main() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(h[i]);
    st.insert(City(-INF, 0)), st.insert(City(-INF, 0));
    st.insert(City(INF, n+1)), st.insert(City(INF, n+1));
    multiset<City>::iterator it;
    for (int i = n; i; --i) {
        City u(h[i], i);
        st.insert(u);
        it = st.find(u);
        tmp[0] = Tmp(*--it), tmp[1] = Tmp(*--it);
        it = st.find(u);
        tmp[2] = Tmp(*++it), tmp[3] = Tmp(*++it);
        for (int j = 0; j < 4; ++j) 
            tmp[j].dth = abs(tmp[j].h - h[i]);
        sort(tmp, tmp+4);
        // na,nb：分别以a,b开车的下一个位置，da,db为其距离
        na[i] = tmp[1].id, da[i] = tmp[1].dth;
        nb[i] = tmp[0].id, db[i] = tmp[0].dth;
        nxt[i][0] = na[i], fa[i][0] = da[i];
    }
    for (int i = 1; i <= n; ++i) {
        nxt[i][1] = nb[na[i]];
        fa[i][1] = fa[i][0], fb[i][1] = db[na[i]];
    }
    for (int i = 2; i <= 19; ++i) {
        for (int u = 1; u <= n; ++u) {
            nxt[u][i] = nxt[nxt[u][i-1]][i-1];
            fa[u][i] = fa[u][i-1] + fa[nxt[u][i-1]][i-1];
            fb[u][i] = fb[u][i-1] + fb[nxt[u][i-1]][i-1];
        }
    }
    int s, x, ans;
    read(x);
    double rat = (double)INF;
    for (int i = 1; i <= n; ++i) {
        solve(i, x);
        if (ans_b == 0) ans_a = INF, ans_b = 1;// 注意ans_b为0的情况
        if ((double)ans_a / (double)ans_b < rat)
            rat = (double)ans_a / (double)ans_b, ans = i;
    }
    printf("%lld\n", ans);
    read(m);
    while (m--) {
        read(s), read(x);
        solve(s, x);
        printf("%lld %lld\n", ans_a, ans_b);
    }
}
}

signed main() {
    RenaMoe::main();
    return 0;
}