北湖深坑 | 感受算法的魅力

今天药忘吃喽~ 2022-12-04 09:26 185阅读 0赞

> ## 5. 北湖深坑 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年09月7日 星期一 09:00</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年09月15日 星期二 09:00</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年10月10日 星期六 23:00</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **Description**
> 
> 十年前，北湖还只是一个深坑，未完成蓄水工作。为了确保蓄水工作的顺利进行，我们需要对北湖的蓄水量进行粗略估计。
> 
> 为了简化运算，我们假设北湖的地面是一维的，每一块宽度都为1，高度是非负整数，那么可以用一个数组来表达一块地面。
> 
> 例如数组 \[0 1 0 2 1 0 1 3 2 1 2 1\] 可以用来表示下图地面：
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]
> 
> 图中绿色代表地面部分，蓝色部分代表蓄水部分，蓄水量为 6。
> 
> **Input**
> 
> 样例输入有多组。
> 
> 第一行输入整数 T 表示有 T 组测试用例。
> 
> 接下来，对于每组用例，输入一个正整数n表示地面宽度，接下来是 n 个数表示地面高度。
> 
> **Output**
> 
> 对于每个用例输出一行一个数字，表示蓄水总量。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>2↵</li> 
>      <li>12↵</li> 
>      <li>0&nbsp;1&nbsp;0&nbsp;2&nbsp;1&nbsp;0&nbsp;1&nbsp;3&nbsp;2&nbsp;1&nbsp;2&nbsp;1↵</li> 
>      <li>5↵</li> 
>      <li>5&nbsp;2&nbsp;3&nbsp;2&nbsp;4↵</li> 
>     </ol></td> 
>    <td> 
>     <ol> 
>      <li>6↵</li> 
>      <li>5↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

此题是一个思维题，你想到了方法，就可以迎刃而解。

### 1、思路分析 ###

**总体思路：分析每一个宽度的蓄水量，然后将他们加起来，就是我们要求的总蓄水量。**

那么重点来了，每一个宽度的蓄水量要如何求得呢?

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

通过观察，我们可以发现，对于**某位置最终蓄水量由其左右两侧的最高处的较小值决定**（这里的左右两侧不一定和该处相邻哈，只要是在左边、在右边就可）

比如说上图：4号位的水量由1号和11号决定、8号位的水量由7号和11号决定...

--------------------

### 2、算法设计 ###

思路出来了，接下来就是编写算法的部分了。我们应该先计算两个数组：left、right。其中，left\[ i \]表示0 ~ i 处的最高点值，即 i 左侧的最高点；right\[ i \] 表示 i ~ n - 1处的最高点值，即 i 右侧的最高点。

然后每一处的储水量可以表示为： min(left\[ i \], right\[ i \]) - a\[ i \]

最后，要注意哈：

1.  我们定义**left、right、h**数组都是在主函数外，也就是**定义成全局变量**。因为主函数内的栈内存比全局内存要少，如果一些大的内存申请定义在主函数内很容易爆栈，也就是爆内存。你提交上去会出现tle（其实本质应该是mle）。 
2.  由于是循环输入每组测试用例，那么你在循环体内一定要记得给他们重新赋初值，不然每次循环会在上次循环的基础上继续计算。

上代码咯~

#include<stdio.h>
    
    long long int left[100000] = {0}, right[100000] = {0}, h[100000] = {0};
    
    int main() {
        int n, T;
        for (scanf("%d", &T); T; T--) {
    
            scanf("%d", &n);
            for (int i = 0; i < n; i++)
                scanf("%lld", &h[i]);
    
            /* 分别计算left和right数组 */
            
            left[0] = h[0];  //边缘情况单独考虑
            right[n - 1] = h[n - 1];   //边缘情况单独考虑
    
            for (int i = 1; i < n - 1; i++)
                if (h[i] < left[i - 1])
                    left[i] = left[i - 1];
                else
                    left[i] = h[i];
            for (int i = n - 2; i > 0; i--)
                if (h[i] < right[i + 1])
                    right[i] = right[i + 1];
                else
                    right[i] = h[i];
                
            //计算总的储水量
            long long int total = 0;  //一定记得赋初值0，不然下一组求值的时候会在上一组答案的基础上加
            for (int i = 1; i < n - 1; i++)
                if (left[i] > right[i])
                    total += right[i] - h[i];
                else
                    total += left[i] - h[i];
    
            printf("%lld\n", total);
        }
    }

--------------------

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/075bc5fac6ac4d60887575e99a893cbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20221123/824901eaa6834ae1b0218a3328453ada.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: /images/20221123/fc795fb912074e4389d575bd214eacce.png