题目描述
春春是一名道路工程师,负责铺设一条长度为 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; } }
|