题目描述
春春是一名道路工程师，负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域，一开始，第 i 块区域下陷的深度为 di。
春春每天可以选择一段连续区间 [L,R]，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0。
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0。
输入格式
输入文件包含两行，第一行包含一个整数 n，表示道路的长度。第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数为 di。
输出格式
输出文件仅包含一个整数，即最少需要多少天才能完成任务。
输入输出样例
输入 #1
输出 #1
说明/提示
【样例解释】
一种可行的最佳方案是，依次选择：[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。
【数据规模与约定】
对于 $30\%$ 的数据，1≤n≤10；
对于 $70\%$ 的数据，1≤n≤1000；
对于 $100\%$ 的数据，1≤n≤100000，0≤di≤10000。
思路
首先，贪心地思考：在区间 [l,r] 中，选择下标 pos，有 $d_{pos}=\min\{d_i|i\in\mathbb N^\ast,l\le i\le r\}$；将 dpos 填平，顺带着就会将 [l,r] 内所有深度都减小 dpos；这时我们就需要分别填 [l,pos−1] 和 [pos+1,r] 两个区间，形成了一个递归的过程。
在 [l,r] 中查询得到 pos，是线段树的区间查询操作；将 pos 位置填平后，需要将 [l,r] 内所有深度减少 dpos，这是线段树的区间修改操作。线段树的结点上维护一个pair值，first为下标，second为道路深度；按照深度向上合并，查询时返回区间内最小深度及其对应的下标。
代码
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
|
#include<iostream>
using namespace std;
typedef long long ll;
const int MAX_SIZE = 100004;
int n;
struct SegmentTree {
int l, r;
pair<int, ll>minOne;
ll lazy;
}tree[MAX_SIZE << 2];
ll d[MAX_SIZE];
void pushUp(int ID);
void pushDown(int ID);
void build(int ID, int l, int r);
void update(int ID, int l, int r, ll v);
pair<int, ll> query(int ID, int l, int r);
ll paveStreet(int l, int r);
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
build(1, 1, n);
cout << paveStreet(1, n) << endl;
return 0;
}
ll paveStreet(int l, int r) {
if (l > r) {
return 0;
}
pair<int, ll> minOne = query(1, l, r);
update(1, l, r, -minOne.second);
return paveStreet(l, minOne.first - 1) + paveStreet(minOne.first + 1, r) + minOne.second;
}
#define lSon ID << 1
#define rSon ID << 1 | 1
void pushUp(int ID) {
if (tree[lSon].minOne.second <= tree[rSon].minOne.second) {
tree[ID].minOne = tree[lSon].minOne;
} else {
tree[ID].minOne = tree[rSon].minOne;
}
}
void build(int ID, int l, int r) {
tree[ID].l = l;
tree[ID].r = r;
if (l == r) {
tree[ID].minOne = make_pair(l, d[l]);
tree[ID].lazy = 0;
return;
}
int mid = l + r >> 1;
build(lSon, l, mid);
build(rSon, mid + 1, r);
pushUp(ID);
}
void pushDown(int ID) {
if (tree[ID].lazy) {
tree[lSon].lazy += tree[ID].lazy;
tree[rSon].lazy += tree[ID].lazy;
tree[lSon].minOne.second += tree[ID].lazy;
tree[rSon].minOne.second += tree[ID].lazy;
tree[ID].lazy = 0;
}
}
void update(int ID, int l, int r, ll v) {
if (l <= tree[ID].l && tree[ID].r <= r) {
tree[ID].minOne.second += v;
tree[ID].lazy += v;
return;
}
pushDown(ID);
int mid = tree[ID].l + tree[ID].r >> 1;
if (l <= mid) {
update(lSon, l, r, v);
}
if (r >= mid + 1) {
update(rSon, l, r, v);
}
pushUp(ID);
}
pair<int, ll> query(int ID, int l, int r) {
if (l <= tree[ID].l && tree[ID].r <= r) {
return tree[ID].minOne;
}
pushDown(ID);
int mid = tree[ID].l + tree[ID].r >> 1;
if (r <= mid) {
return query(lSon, l, r);
} else if (l >= mid + 1) {
return query(rSon, l, r);
} else {
pair<int, ll> tLeft = query(lSon, l, mid);
pair<int, ll> tRight = query(rSon, mid + 1, r);
return tLeft.second <= tRight.second ? tLeft : tRight;
}
}
|
微信
支付宝
QQ
