P1081

题目简述

有一排高低不同的城市 城市距离=高度差

A和B自左向右开车旅行(出发点可以变)

A、B的开车风格:

1.A会前往右边距他第二近的城市
2.B会前往右边最近的城市
3.A和B开过的总里程不超过$X$

询问:

1.给定一个$X$ 求出从哪个城市出发 $A$的路程/$B$的路程 最大

2.给定$X_i$和出发城市$S_i$ 求$A$和$B$分别开的距离数

倍增

在没有修改的RMQ问题(区间最值问题) 基于倍增的ST表可以做到$O(1)$查询和$O(nlogn)$预处理

拿最大值来说我们用$Max[i][j]$表示,从$i$位置开始的$2^j$个数中的最大值,例如$Max[i][1]$表示的是$i$位置和$i+1$位置中两个数的最大值(也就是说当前位置是被包含进$2^j$个数去的)

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值

比如

transfer

$$
f[i][j] = \max{f[i][j - 1], f[i + (1 << (j - 1))][j - 1]}
$$

上面就是一般倍增用来求最大值时候的转移式(没什么用不用看

另一个倍增的常见应用就是$LCA$

通过倍增的思想向上跳

那么

这道题目

我们可以利用倍增向右跳

但是我们要先处理出$f[i][0]$

也就是从任意一个城市开始 走一步到达的城市

首先就要处理出对于到达每一个城市$a_i$ $A$和$B$的下一步会去哪里

这一步可以用一个双向链表 开始的时候将城市从低到高排序并且相邻的相连

就像这个

image.png

排序完之后的顺序是 3 1 2 4

每一个点都与旁边相连

之后从原来顺序开始处理 不断选出A和B的选择然后删除这个节点 就可以处理完 nanb数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool left() {
if (!l) return 0;
if (!r) return 1;
return d[j].v-d[l].v<=d[r].v-d[j].v;
}
for (int i = 1; i <= n; i++) {
j = p[i]; l = d[j].l; r = d[j].r;
if (left())
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;
if (r) d[r].l = l;
}

$na[i]$表示在$i$号城市时,$A$的下一个城市

之后就可以将A开一天B开一天当作一步

用倍增来初始化 $f[i][j]$从$i$号城市开始 走$2^j$大步后到达的城市

$sta[i][j]$表示从$i$号城市开始 走$2^j$大步后 A走过的路程(是一个累计量

$stb$数组同理

这样我们就可以用倍增枚举和找到符合要求的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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];
//因为f表示的是一大步(ab各一步) 所以可能A还可以走一步

}

总的代码

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
#include <bits/stdc++.h>

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 left() {
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() {
for (int j = 1; j <= 19; j++) {
for (int 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() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif

long long x;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &d[i].v);

for (int i = 1; i <= n; i++)
d[i].i = i;

sort(d + 1, d + n + 1);

for (int i = 1; i <= n; i++)
p[d[i].i] = i;//记录原本的顺序 p[i]存放了原来在i位置的城市排序完的位置

for (int i = 1; i <= n; i++)
d[i].l = i-1, d[i].r = i+1;
d[1].l = d[n].r = 0;

for (int i = 1; i <= n; i++) {
j = p[i]; l = d[j].l; r = d[j].r;
if (left())
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;
if (r) d[r].l = l;
}//na, nb是对于原来的第i号城市 A和B的下一个目的地

for (int i = 1; i <= n; i++)
printf("%d ", na[i]);
puts("");
for (int i = 1; i <= n; i++)
printf("%d ", nb[i]);
puts("");

for (int i = 1; i <= n; i++) {
f[i][0] = nb[na[i]];
//A和B一起倍增
stA[i][0] = abs(d[p[i]].v - d[p[na[i]]].v);
stB[i][0] = abs(d[p[na[i]]].v - d[p[f[i][0]]].v);
//A和B 在A一步B一部之后 分别移动的的距离
}
make_st();

scanf("%lld%d", &x, &m);
for (int 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 (int i = 1; i <= m; i++) {
scanf("%d%lld", &j, &x);
getab(x, j);
printf("%d %d\n", a, b);
}
return 0;
}

评论