|
link
思维
题意
给出一个序列
a
1
,
a
2
,
.
.
.
,
a
n
a_1,a_2,...,a_n
a1?,a2?,...,an? 为
1
～
n
1～n
1～n 的全排列。
i
,
j
i,j
i,j 之间存在一条无向边当且仅当
a
i
,
a
j
a_i,a_j
ai?,aj? 恰好是
a
i
,
.
.
.
,
a
j
a_i,...,a_j
ai?,...,aj? 这些数的最小值和最大值（一个最小一个最大）。每条边的长度均为1，问从
1
1
1 到
n
n
n 最短距离是多少。
1
≤
n
≤
2.5
×
1
0
5
1\leq n\leq2.5\times10^5
1≤n≤2.5×105。
思路
设
d
i
s
(
x
,
y
)
dis(x,y)
dis(x,y) 表示
x
x
x 和
y
y
y 之间的最短路长度。
考虑
a
i
=
n
a_i = n
ai?=n 的位置，并假设
i
≠
1
,
i
≠
n
i \neq 1,i\neq n
i?=1,i?=n ，显而易见的，从
1
→
n
1\to n
1→n ,必须要经过
i
i
i 点。同理考虑
a
j
=
1
a_j=1
aj?=1 的位置，类似的，必须经过
j
j
j 点，则有
d
i
s
(
x
,
y
)
=
d
i
s
(
1
,
i
)
+
1
+
d
i
s
(
j
,
n
)
dis(x,y)=dis(1,i) + 1 + dis(j, n)
dis(x,y)=dis(1,i)+1+dis(j,n)这里假设了
i
<
j
i<j
i<j，如果
j
>
i
j>i
j>i 的话也一样。中间的
1
1
1 即为
d
i
s
(
i
,
j
)
dis(i,j)
dis(i,j)，因为
a
i
,
a
j
a_i,a_j
ai?,aj? 分别为
n
n
n 和
1
1
1，所以显然有边可以一步到达。
接下来继续递归处理
d
i
s
(
1
,
i
)
dis(1,i)
dis(1,i) 和
d
i
s
(
j
,
n
)
dis(j,n)
dis(j,n) 。只要找到区间的最小值和最大值并继续递归就可以了。
只需要预处理前缀和后缀的最小值对应的下标就可以了。 时间复杂度
O
(
n
)
O(n)
O(n) 。
代码
int n;
int a[maxn], id[maxn];
int l_min[maxn], l_max[maxn];
int r_min[maxn], r_max[maxn];
int dfs(int l, int r) {
if(l == r) return 0;
if(l != 1 && r != n) return 1;
int L, R;
if(l == 1) {
L = min(l_min[r], l_max[r]);
R = max(l_min[r], l_max[r]);
}
else {
L = min(r_min[l], r_max[l]);
R = max(r_min[l], r_max[l]);
}
if(l == L && r == R) return 1;
return dfs(l, L) + dfs(L, R) + dfs(R, r);
}
void solve() {
cin >> n;
l_min[0] = r_min[n+1] = INF;
l_max[0] = r_max[n+1] = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
l_min[i] = min(l_min[i-1], a[i]);
l_max[i] = max(l_max[i-1], a[i]);
id[a[i]] = i;
}
for(int i = n; i; i--) {
r_max[i] = max(r_max[i+1], a[i]);
r_min[i] = min(r_min[i+1], a[i]);
}
for(int i = 1; i <= n; i++) {
l_min[i] = id[l_min[i]];
r_min[i] = id[r_min[i]];
l_max[i] = id[l_max[i]];
r_max[i] = id[r_max[i]];
}
cout << dfs(1, n) << endl;
}
|