「LAOI-1」积水

题意

给一个长度为 n 的正整数序列，表示地形高度。

下雨后每个位置的积水量按经典接雨水模型计算：

等于 min(左侧最高, 右侧最高) - 当前高度
如果这个值小于等于 0，则该位置不积水

现在允许把 恰好一个位置 的高度修改成任意正整数，问修改后最少还能积多少水。

思路

先看一个最直接的小数据暴力：

cpp

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

const int MAXN = 205;

int T;
int n;
long long a[MAXN];
long long b[MAXN];
long long left_max_arr[MAXN];
long long right_max_arr[MAXN];

// brute.cpp：小数据暴力解。
// 做法是枚举被修改的位置，再枚举修改后的高度，直接重新计算总积水量。

long long calc_water(long long arr[]) {
    left_max_arr[0] = 0;
    for (int i = 1; i <= n; i++) {
        left_max_arr[i] = max(left_max_arr[i - 1], arr[i]);
    }

    right_max_arr[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        right_max_arr[i] = max(right_max_arr[i + 1], arr[i]);
    }

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        long long level = min(left_max_arr[i], right_max_arr[i]);
        if (level > arr[i]) {
            sum += level - arr[i];
        }
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        long long mx = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            mx = max(mx, a[i]);
        }

        // 小数据对拍时，枚举到 max(a)+1 已经足够。
        // 因为把某个位置改得更高，不会比改成这个范围内更优。
        long long answer = (long long)4e18;
        for (int pos = 1; pos <= n; pos++) {
            for (int new_height = 1; new_height <= mx + 1; new_height++) {
                for (int i = 1; i <= n; i++) {
                    b[i] = a[i];
                }
                b[pos] = new_height;
                answer = min(answer, calc_water(b));
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

暴力的问题在于：

要枚举修改位置
还要枚举新高度
每次修改后还要重新算整条序列的积水

肯定不能用于正式数据。

这题的关键有两个。

第一，固定修改位置 i 后，最优新高度其实不用枚举。

设：

L 是 i 左边所有位置的最高值
R 是 i 右边所有位置的最高值

那么最优新高度一定可以直接取成：

text

1max(1, min(L, R))

因为高于这个值没有额外收益，低于这个值本质上只是更彻底地失去挡板作用。

第二，位置 i 变矮以后，不会影响整张图，只会影响真正把它当挡板的那些位置。

对右边来说，只有当 a[i] 是“从左往右扫描时出现的新高点”时，它才可能成为右边一些位置的左挡板。

而它负责的右侧区间，恰好是：

从 i+1 开始
到右边第一个高度 >= a[i] 的位置之前结束

因为一旦遇到不低于 a[i] 的柱子，后面的左挡板就不再依赖 i。

左边完全对称。

所以整题做法是：

预处理前后缀最高值
算出原始每个位置的积水与总积水
用单调栈求每个位置左右最近的 >=
线性扫描所有“关键挡板”，分别计算它改低后对右边、左边造成的变化
枚举修改位置，按贡献合并答案

代码

cpp

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int T;
int n;
long long a[MAXN];

// left_max[i] 表示下标 i 左侧(不含 i)的最高高度
long long left_max_arr[MAXN];
// right_max[i] 表示下标 i 右侧(不含 i)的最高高度
long long right_max_arr[MAXN];

// pre[i] 表示 1..i 的前缀最高值
long long pre_max[MAXN];
// suf[i] 表示 i..n 的后缀最高值
long long suf_max[MAXN];

// water[i] 表示原序列在位置 i 产生的积水量
long long water_arr[MAXN];
// pre_water[i] 表示 water 的前缀和
long long pre_water[MAXN];

// nxt_ge[i] 表示 i 右边第一个高度 >= a[i] 的位置，不存在则为 n+1
int nxt_ge[MAXN];
// pre_ge[i] 表示 i 左边第一个高度 >= a[i] 的位置，不存在则为 0
int pre_ge_pos[MAXN];

// 如果把 i 变矮，会影响它右边一段位置的积水：
// old_right[i] 是这一段在原序列中的积水总量
// new_right[i] 是删掉 i 这块挡板后，这一段新的积水总量
long long old_right[MAXN];
long long new_right[MAXN];

// 同理，影响左边一段位置时使用下面两个数组
long long old_left[MAXN];
long long new_left[MAXN];

int stk[MAXN];

void build_prefix_suffix() {
    pre_max[0] = 0;
    for (int i = 1; i <= n; i++) {
        pre_max[i] = max(pre_max[i - 1], a[i]);
    }

    suf_max[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        suf_max[i] = max(suf_max[i + 1], a[i]);
    }

    for (int i = 1; i <= n; i++) {
        left_max_arr[i] = pre_max[i - 1];
        right_max_arr[i] = suf_max[i + 1];
    }
}

long long build_original_water() {
    long long total = 0;
    pre_water[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long level = min(pre_max[i], suf_max[i]);
        if (level > a[i]) {
            water_arr[i] = level - a[i];
        }
        else {
            water_arr[i] = 0;
        }
        total += water_arr[i];
        pre_water[i] = pre_water[i - 1] + water_arr[i];
    }
    return total;
}

void build_nearest_ge() {
    int top = 0;
    for (int i = n; i >= 1; i--) {
        while (top > 0 && a[stk[top]] < a[i]) {
            top--;
        }
        if (top == 0) {
            nxt_ge[i] = n + 1;
        }
        else {
            nxt_ge[i] = stk[top];
        }
        stk[++top] = i;
    }

    top = 0;
    for (int i = 1; i <= n; i++) {
        while (top > 0 && a[stk[top]] < a[i]) {
            top--;
        }
        if (top == 0) {
            pre_ge_pos[i] = 0;
        }
        else {
            pre_ge_pos[i] = stk[top];
        }
        stk[++top] = i;
    }
}

void build_right_change() {
    for (int i = 1; i <= n; i++) {
        old_right[i] = 0;
        new_right[i] = 0;
    }

    int i = 1;
    while (i <= n) {
        // 只有“从左向右看见的新高点”才可能作为右侧许多位置的左挡板
        if (a[i] > pre_max[i - 1]) {
            int r = nxt_ge[i];
            int L = i + 1;
            int R;
            if (r <= n) {
                R = r - 1;
            }
            else {
                R = n;
            }

            if (L <= R) {
                old_right[i] = pre_water[R] - pre_water[L - 1];

                // 把 i 改低到不超过外部挡板后，
                // 这段区间的左侧最高值会退回到 pre_max[i - 1]，
                // 然后从左往右重新维护前缀最高值即可。
                long long cur_left_max = pre_max[i - 1];
                long long sum = 0;
                for (int j = L; j <= R; j++) {
                    cur_left_max = max(cur_left_max, a[j]);
                    long long level = min(cur_left_max, suf_max[j]);
                    if (level > a[j]) {
                        sum += level - a[j];
                    }
                }
                new_right[i] = sum;
            }

            i = R + 1;
        }
        else {
            i++;
        }
    }
}

void build_left_change() {
    for (int i = 1; i <= n; i++) {
        old_left[i] = 0;
        new_left[i] = 0;
    }

    int i = n;
    while (i >= 1) {
        // 对称地处理“从右向左看见的新高点”
        if (a[i] > suf_max[i + 1]) {
            int l = pre_ge_pos[i];
            int L;
            if (l >= 1) {
                L = l + 1;
            }
            else {
                L = 1;
            }
            int R = i - 1;

            if (L <= R) {
                old_left[i] = pre_water[R] - pre_water[L - 1];

                long long cur_right_max = suf_max[i + 1];
                long long sum = 0;
                for (int j = R; j >= L; j--) {
                    cur_right_max = max(cur_right_max, a[j]);
                    long long level = min(pre_max[j], cur_right_max);
                    if (level > a[j]) {
                        sum += level - a[j];
                    }
                }
                new_left[i] = sum;
            }

            i = L - 1;
        }
        else {
            i--;
        }
    }
}

long long solve_one_case() {
    build_prefix_suffix();
    long long total_water = build_original_water();
    build_nearest_ge();
    build_right_change();
    build_left_change();

    long long answer = (long long)4e18;

    for (int i = 1; i <= n; i++) {
        // 位置 i 自己的最优新高度一定取：
        // max(1, min(左侧外部最高, 右侧外部最高))
        // 这样既不会比需要的更高，也不会违反“正整数”限制。
        long long new_height = min(left_max_arr[i], right_max_arr[i]);
        if (new_height < 1) {
            new_height = 1;
        }

        long long self_water = 0;
        long long self_level = min(max(left_max_arr[i], new_height), max(right_max_arr[i], new_height));
        if (self_level > new_height) {
            self_water = self_level - new_height;
        }

        long long cand = total_water;
        cand -= water_arr[i];
        cand -= old_right[i];
        cand -= old_left[i];
        cand += self_water;
        cand += new_right[i];
        cand += new_left[i];

        answer = min(answer, cand);
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        cout << solve_one_case() << '\n';
    }

    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

总结

这题表面上是“修改一个点后重新算接雨水”，但真正要抓住的是：

固定位置时，最优新高度可以直接确定
改低一个挡板，只会影响它左右各一段连续区间

只要把“全局重算”改成“局部重算”，整题就能在线性时间完成。

目录

题意

思路

代码

复杂度

总结