P1010 67的心下起了大雨

一.解题思路

1.碎碎念

最近一直单曲循环 喜欢-阿肆https://y.qq.com/n/yqq/song/0015EQT708bZlQ.html

好好听呜呜呜听😭了

既然这么好听那就来编一下这个题解吧！

对了！看完题解别直接走哇点个赞求求你了！！！

呜呜呜写题解的时候码蹄杯出结果了，呜呜呜四银一铜，恭喜他们几个进决赛（咬牙切齿版

金银进决赛主包铜奖继🏀杯后再一次失之交臂啊啊啊啊（这件事告诉我们打比赛一定要看排行榜，不然真的会丢大分！！！

2.题目分析

通读完题目，发现这是一道接雨水的题目，我们只需要理解这道题定义的凹陷即可，由题目可知，只要这一块形成一个坑（水深大于0），就是一处凹陷

例如 1 ** 1 这中间的**就是凹陷

​ 0101110

注意：即使中间有凸起，只要凸起的高度低于两侧的最高点（即该处也有积水），水面就会漫过凸起，整个区域仍算作同一个凹陷

而凹陷就以为着可以积水，不过题目并非要求有几格水深，所以只需要做简单的含水判断就好啦

因此，我们只需要找到积水大于0的连续段，就是一处凹陷

理论存在，实践开始！

3.算法实现

1.先预处理左侧及右侧最大值

**L[i]=max(L[i−1],h[i−1])，其中 L[0]=0

R[i]=max(R[i+1],h[i+1])，其中 R[n−1]=0

注意：此处最大值并不包含i这一点

2.计算每个位置的积水量

water[i]=max(0,min(L[i],R[i])−h[i])

3.通过flag标记是否第一次进入该积水区域

4.复杂度

1.时间：O(n)

2.空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    vector<int> h(n);
    for(int i = 0;i<n;++i){
        cin>>h[i];
    }
    
    int ans = 0;
    vector<int> l_max(n,0);
    vector<int> r_max(n,0);

    for(int i = 1;i<n;++i){
        l_max[i] = max(l_max[i-1],h[i-1]);
    }
    for(int i = n-2;i>=0;--i){
        r_max[i] = max(r_max[i+1],h[i+1]);
    }

    bool flag = 0;
    for(int i = 0;i<n;++i){
        int area = max(0LL,min(l_max[i],r_max[i])-h[i]);
        if(area > 0){
            if(!flag){
                ans++;
                flag = 1; 
            }
        }else{
            flag = 0;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！

python解 67 的内心积水区域

这个是python的题解，C++的题解如果没有的话去群里面压力flying他会帮你们写的不过这个解题思考可以看看或许对你们有一点启发.

算法思路

本题是经典的接雨水问题升级版——不仅要算每个位置的水深，还要统计连通区域的数量。

分析

1. 计算每个位置的水深

利用木桶效应：每个柱子能接多高的水，取决于它左右两边最高柱子的较小值。

• 预处理 left_max[i]：表示 $h_0$ 到 $h_{i-1}$ 中的最大值。
• 预处理 right_max[i]：表示 $h_{i+1}$ 到 $h_{n-1}$ 中的最大值。
• 位置 $i$ 的水深：water = max(0, min(left_max[i], right_max[i]) - h[i])

2. 统计连续的积水区域

用一个变量 in_Water 表示当前是否正处于一个积水区域内部。
遍历所有位置：

• 若 water > 0 且 in_Water == False：发现新区域的起点，计数器加一，并将 in_Water 置为 True。
• 若 water == 0：离开区域，in_Water 置为 False。

这样就能准确地将连续的水深格子合并成一个区域。

复杂度

• 时间复杂度：$O(n)$，三次线性扫描。（左扫描、右扫描、统计）
• 空间复杂度：$O(n)$，需要两个长度为 $n$ 的辅助数组。

代码

def count_water_regions(n, h):
    """
    统计积水区域的数量
    
    参数:
    n: 高度序列长度
    h: 高度序列列表
    
    返回:
    积水区域的数量
    """
    # 预处理左侧最高值
    left_max = [0] * n
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], h[i-1])
    
    # 预处理右侧最高值
    right_max = [0] * n
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], h[i+1])
    
    # 统计连续的积水区域
    regions = 0
    in_water = False
    
    for i in range(n):
        # 计算当前位置的水深
        water = max(0, min(left_max[i], right_max[i]) - h[i])
        
        if water > 0 and not in_water:
            # 发现新的积水区域
            regions += 1
            in_water = True
        elif water == 0:
            # 离开积水区域
            in_water = False
    
    return regions


def main():
    # 读取输入
    n = int(input())
    h = list(map(int, input().split()))
    
    # 计算并输出结果
    result = count_water_regions(n, h)
    print(result)


if __name__ == "__main__":
    main()