【题解】P1081 [NOIP2012 提高组] 开车旅行

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

给出一些城市，从西向东排成一排，每个城市有一个海拔\(h_i\)，定义城市\(i,j\)间的距离位海拔之差的绝对值，即\(d(i,j)=|h(i)-h(j)|\)。

小\(A\)和小\(B\)轮流开车，第一天小\(A\)开车，之后每天换一次。他们计划选择一个城市\(s\)作为起点，一直向东，并且最多行驶\(x\)公里就结束旅行。

小 \(B\) 总是沿着前进方向选择一个最近的城市作为目的地，而小 \(A\) 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）

求：

  1. 对于一个给定的 \(x=x_0\)，从哪一个城市出发，小\(A\)开车行驶的路程总数与小\(B\)行驶的路程总数的比值最小（如果小\(B\) 的行驶路程为 \(0\)，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小\(A\)开车行驶的路程总数与小\(B\)行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

  2. 对任意给定的\(x=x_i\) 和出发城市 \(s_i\)，小\(A\)开车行驶的路程总数以及小\(B\)行驶的路程总数。

\(1 \le n,m \le 10^5, -10^9 \le h_i \le 10^9\)

\(1 \le s_i \le n, 0 \le x_i \le 10^9\)

分析

首先，想到预处理出每个城市的距离第一\(min1\)和第二近\(min2\)的城市。不难想到，将\(h_i\)排序，那么对于\(i\)，\(min1\)和\(min2\)一定在\(i-2,i-1,i+1,i+2\)中产生。还需要考虑城市间的方向，即\(i\)必须在\(min1,min2\)的西边。

首先，记下城市排序之后的位置。从节点\(1\)，开始预处理\(min1,min2\)。显然，第一个节点永远在其他节点的西边，每次预处理完一个节点后将它删除即可。

这样，在\(O(n)\)的复杂度完成了预处理，选择用双向链表实现，这一部分也可以用C++ STL中的Set或手写平衡树实现。

接下来继续分析。题目中需要求：

对于一个给定的 \(x=x_0\)，从哪一个城市出发，小\(A\)开车行驶的路程总数与小\(B\)行驶的路程总数的比值最小。

现在需要求出出发的城市和行驶的天数。如果纯模拟开车过程一定会超时，于是想到倍增dp。

首先定义状态：

\(f(i,j,k)\)表示开车\(2^i\)天，从城市\(j\)出发到达的城市，\(k=0\)表示小$ A\(开车，\)k=1\(表示小\)B\(开车。同样，定义\)da(i,j,k),db(i,j,k)\(分别表示\)A,B$开车\(2^i\)天，从城市\(j\)出发走过的距离，\(k=0\)表示轮到小$ A\(开车，\)k=1\(表示轮到小\)B$开车。

接下来考虑初始化：

对于\(f\)，有：

\(f(0,j,0)=min2_j\)

\(f(0,j,1)=min1_j\)

对于\(da\)，有：

\(da(0,j,0)=|h(j)-h(min2(j))|\)

\(db(0,j,1)=0\)

对于\(db\)有：

\(db(0,j,0)=0\)

\(db(0,j,1)=|h(j)-h(min1(j))|\)

接下来考虑转移方程：

根据倍增的套路，大部分是分别针对前一半和后一半进行处理。

特别的，当\(i=1\)时，\(2^i=2\)前后由不同的人开车，因此转移时要把\(k\)取反：

\(f(i,j,k)=f(i-1,f(i-1,j,k),k\bigoplus 1)\)

当\(i>1\)时，转移：

\(f(i,j,k)=f(i-1,f(i-1,j,k),k)\)

同理，\(da\)和\(db\)的转移也可以这样理解：总路程=前半段路程+后半段路程

\(da(i,j,k)=da(i-1,j,k)+da(i-1,da(i-1,j,k),k\bigoplus 1),(i=1)\)

\(da(i,j,k)=da(i-1,j,k)+da(i-1,da(i-1,j,k),k),(i>1)\)

\(db(i,j,k)=db(i-1,j,k)+db(i-1,db(i-1,j,k),k\bigoplus 1),(i=1)\)

\(db(i,j,k)=db(i-1,j,k)+db(i-1,db(i-1,j,k),k),(i>1)\)

最后考虑求答案：

计算从城市\(c\)出发，最多走\(x\)的距离，小\(A\)和小\(B\)走的距离\(la,lb\)。这里用倍增的常规思路即可，按照\(i\)从大到小枚举，如果走完\(2^i\)天，总路程不超过\(x\)，就走过去，更新\(la\)和\(lb\)。

题目中第一问问的是从哪个起点出发\(la,lb\)比值最小，第二问问的是\(la,lb\)的值。

实现

定义用到的元素，结构体用来建双向链表：

1
2
3
4
int n, m, pos[N], min2[N], min1[N], da[25][100005][2], db[25][100005][2], f[25][100005][2], la, lb;
struct nod {
    int h, l, r, id;
} g[N];

输入和双向链表的初始化，注意在\(pos\)中记录每座城市排序完的位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = read();
for (int i = 1; i <= n; i++) {
    g[i].h = read();
    g[i].id = i;
}

//建双向链表
sort(g + 1, g + n + 1, cmp);
for (int i = 1; i <= n; i++) {
    g[i].l = i - 1;
    g[i].r = i + 1;
    pos[g[i].id] = i;
}
g[1].l = g[n].r = 0;

接着，预处理出\(min1\)和\(min2\)：

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i < n; i++) {
    int p = pos[i], p1 = g[p].l, p2 = g[p].r;
    if (p1 && (g[p].h - g[p1].h <= g[p2].h - g[p].h || !p2)) {
        min1[i] = g[p1].id;
        min2[i] = cho(g[p1].l, p2, p);
    } else {
        min1[i] = g[p2].id;
        min2[i] = cho(p1, g[p2].r, p);
    }
    del(p);
}

其中，\(cho()\)函数用来选择最近的城市，\(del()\)函数用于删除双向链表中的元素：

1
2
3
4
5
6
7
8
9
10
int cho(int a, int b, int c) {
    if (!a) return g[b].id;
    if (!b) return g[a].id;
    if (g[c].h - g[a].h <= g[b].h - g[c].h) return g[a].id;
    else return g[b].id;
}
void del(int in) {
    g[g[in].l].r = g[in].r;
    g[g[in].r].l = g[in].l;
}

之后是倍增dp的部分，首先将dp数组初始化：

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= n; i++) {
    if (min2[i]) {
        f[0][i][0] = min2[i];
        da[0][i][0] = abs(g[pos[i]].h - g[pos[min2[i]]].h);
        db[0][i][0] = 0;
    }
    if (min1[i]) {
        f[0][i][1] = min1[i];
        da[0][i][1] = 0;
        db[0][i][1] = abs(g[pos[i]].h - g[pos[min1[i]]].h);
   
}

然后进行转移，注意\(i=1\)时的特殊情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = 1; i <= 18; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 0; k <= 1; k++) {
            int l;
            if (i == 1) l = k ^ 1;
            else l = k;
            if (f[i - 1][j][k]) f[i][j][k] = f[i - 1][f[i - 1][j][k]][l];
            if (f[i][j][k]) {
                da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][l];
                if (f[i][j][k]) {
                    da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][l];
                    db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][l];
                }

            }
        }
    }
}

之后，解决题目中的第一问：

对于一个给定的 \(x=x_0\)，从哪一个城市出发，小\(A\)开车行驶的路程总数与小\(B\)行驶的路程总数的比值最小（如果小\(B\) 的行驶路程为 \(0\)，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小\(A\)开车行驶的路程总数与小\(B\)行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

1
2
3
4
5
6
int m = read();
while (m--) {
    s = read(), x = read();
    calc(s, x);
    printf("%lld %lld\n", la, lb);
}

其中\(cal()\)函数是用来计算\(A,B\)走过的路程，并更新\(la,lb\)的，倍增的板子方法。

1
2
3
4
5
6
7
8
9
10
11
12
void calc(int s, long long x) {
    la = lb = 0;
    int k = 0;
    for (int i = 18; i >= 0; i--) {
        if (f[i][s][k] && da[i][s][k] + db[i][s][k] <= x) {
            x -= da[i][s][k] + db[i][s][k];
            la += da[i][s][k], lb += db[i][s][k];
            if (!i)k ^= 1;
            s = f[i][s][k];
        }
    }
}

最后解决第二问：

对任意给定的\(x=x_i\) 和出发城市 \(s_i\)，小\(A\)开车行驶的路程总数以及小\(B\)行驶的路程总数。

1
2
3
4
5
while (m--) {
    s = read(), x = read();
    calc(s, x);
    printf("%lld %lld\n", la, lb);
}

附完整代码\((932ms,40.91mb)\)

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>

using namespace std;
const int N = 100005;
int pos[N], min2[N], min1[N], da[25][100005][2], db[25][100005][2], f[25][100005][2], la, lb;
int n, m;

int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

//双向链表
struct nod {
    int h, l, r, id;
} g[N];

void del(int in) {
    g[g[in].l].r = g[in].r;
    g[g[in].r].l = g[in].l;
}

int cho(int a, int b, int c) {
    if (!a) return g[b].id;
    if (!b) return g[a].id;
    if (g[c].h - g[a].h <= g[b].h - g[c].h) return g[a].id;
    else return g[b].id;
}

void calc(int s, long long x) {
    la = lb = 0;
    int k = 0;
    for (int i = 18; i >= 0; i--) {
        if (f[i][s][k] && da[i][s][k] + db[i][s][k] <= x) {
            x -= da[i][s][k] + db[i][s][k];
            la += da[i][s][k], lb += db[i][s][k];
            if (!i)k ^= 1;
            s = f[i][s][k];
        }
    }
}

bool cmp(nod a, nod b) {
    return a.h < b.h;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        g[i].h = read();
        g[i].id = i;
    }
    
    //建双向链表
    sort(g + 1, g + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        g[i].l = i - 1;
        g[i].r = i + 1;
        pos[g[i].id] = i;
    }
    g[1].l = g[n].r = 0;
    
    //预处理第一和第二近的
    for (int i = 1; i < n; i++) {
        int p = pos[i], p1 = g[p].l, p2 = g[p].r;
        if (p1 && (g[p].h - g[p1].h <= g[p2].h - g[p].h || !p2)) {
            min1[i] = g[p1].id;
            min2[i] = cho(g[p1].l, p2, p);
        } else {
            min1[i] = g[p2].id;
            min2[i] = cho(p1, g[p2].r, p);
        }
        del(p);
    }
    
    //倍增dp
    //初始化
    for (int i = 1; i <= n; i++) {
        if (min2[i]) {
            f[0][i][0] = min2[i];
            da[0][i][0] = abs(g[pos[i]].h - g[pos[min2[i]]].h);
            db[0][i][0] = 0;
        }
        if (min1[i]) {
            f[0][i][1] = min1[i];
            da[0][i][1] = 0;
            db[0][i][1] = abs(g[pos[i]].h - g[pos[min1[i]]].h);
        }
    }
    //转移
    for (int i = 1; i <= 18; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k <= 1; k++) {
                int l;
                if (i == 1) l = k ^ 1;
                else l = k;
                if (f[i - 1][j][k]) f[i][j][k] = f[i - 1][f[i - 1][j][k]][l];
                if (f[i][j][k]) {
                    da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][l];
                    if (f[i][j][k]) {
                        da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][l];
                        db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][l];
                    }

                }
            }
        }
    }
    
    //第一问：枚举起点
    long long x;
    int s;
    scanf("%lld", &x);
    int p = 0;
    long long ansa = 1, ansb = 0;
    for (int i = 1; i <= n; i++) {
        calc(i, x);
        if (!lb) la = 1;
        if (la * ansb < lb * ansa || (la * ansb == lb * ansa && g[pos[i]].h > g[pos[p]].h))
            ansa = la, ansb = lb, p = i;
    }
    printf("%d\n", p);
    
    //第二问：a，b行驶的距离
    int m = read();
    while (m--) {
        s = read(), x = read();
        calc(s, x);
        printf("%lld %lld\n", la, lb);
    }
    return 0;
}