P1318 积水面积【洛谷算法习题】

P1318 积水面积网页链接P1318 积水面积题目描述一组正整数分别表示由正方体叠起的柱子的高度。若某高度值为x xx表示由x xx个正立方的方块叠起如下图0 ≤ x ≤ 5000 0 \le x \le 50000≤x≤5000。找出所有可能积水的地方图中蓝色部分统计它们可能积水的面积总和计算的是图中的横截面积。一个立方体的位置为一个单位面积。如图柱子高度变化为0 1 0 2 1 2 0 0 2 0。图中蓝色部分为积水面积共有6 66个单位面积积水。输入格式两行第一行n nn表示有n nn个数3 ≤ n ≤ 10000 3 \le n \le 100003≤n≤10000。第2 22行连续n nn个数表示依次由正方体叠起的高度保证首尾为0 00。输出格式一个数可能积水的面积。输入输出样例 #1输入 #110 0 1 0 2 1 2 0 0 2 0输出 #16解题思路本题是经典的接雨水问题核心采用双数组预处理法计算总积水面积。对于每个柱子位置能积存的水量由左侧最高柱子和右侧最高柱子中的较小值决定用该值减去当前柱子高度即为积水量。首先正向遍历数组预处理出每个位置左侧的最大高度数组l再反向遍历数组预处理出每个位置右侧的最大高度数组r。最后遍历所有位置累加每个位置的有效积水量结果非负最终得到总积水面积。算法时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)简洁高效完美适配题目数据范围。总结核心逻辑单个位置积水量 min(左侧最大高度, 右侧最大高度) - 当前柱子高度结果≥0。关键操作预处理左右最大高度数组、遍历累加有效积水量。效率保障线性时间遍历无冗余计算轻松处理n ≤ 10000 n \le 10000n≤10000的数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a[10001]{0},l[10001]{0},r[10001]{0},n,sum0;cinn;for(ll i1;in;i){cina[i];l[i]max(l[i-1],a[i]);}for(ll in;i1;i--)r[i]max(r[i1],a[i]);for(ll i1;in;i){if(min(l[i],r[i])-a[i]0)sum0;elsesummin(l[i],r[i])-a[i];}coutsum;return0;}