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

你的名字 2022-12-05 04:55 127阅读 0赞

> ## 4. 北湖挖坑 ##
> 
> <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，高度是非负整数，那么可以用一个数组来表达一块地面。
> 
> 一开始北湖是一片平地，每一块的高度为[![h][]][h 1]。下图是[![h=3][h_3]][h_3_h_3]的情况，用数组表示为\[3,3,3,3,3,3,3,3,3,3,3,3\]。
> 
> ![20200909085024269.png][]
> 
> 施工队根据图纸想将其挖成凹凸不平的形状，如下图所示，数组表示为\[0,1,0,2,1,0,1,3,2,1,2,1\]。
> 
> ![20200909085024262.png][]
> 
> 施工队有一台挖土机，每一天挖土机可以将连续一段区间挖掉一格土。包工头小张想尽快完成任务，请你告诉他将平整的土地挖成图纸所示的情况最少需要多少天？
> 
> **Input**
> 
> 第一行输入两个整数[![n(1 \\leq n \\leq 100000 ),h(1 \\leq h \\leq 1000000 )][n_1 _leq n _leq 100000 _h_1 _leq h _leq 1000000]][n_1 _leq n _leq 100000 _h_1 _leq h _leq 1000000 _n_1 _leq n _leq 100000 _h_1 _leq h _leq 1000000]。表示北湖的总宽度和初始每一块的高度。
> 
> 接下来一行[![n][]][n 1]个整数[![a\_i (0 \\leq a\_i \\leq h )][a_i _0 _leq a_i _leq h]][a_i _0 _leq a_i _leq h _a_i _0 _leq a_i _leq h]，表示图纸上每一个位置的高度。
> 
> **Output**
> 
> 一个整数表示最少几天能将北湖挖好。
> 
> **Notes**
> 
> 9天挖土的区间为\[1,7\]，\[1,3\]，\[5,7\]，\[1,1\]，\[3,3\]，\[6,6\]，\[9,12\]，\[10,10\]，\[12,12\]。
> 
>  
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=201978&amp;test=129498&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>12&nbsp;3↵</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> 
>     </ol></td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=201978&amp;test=129498&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>9↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

这题暴力、二分都会 tle（超时），那我们需要更聪明的办法，让我们代码的时间复杂度降低：

对于题中给出的用例，我们需要挖掉的部分如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

为了方便思考，我们将上图**倒过来**考虑，不用担心，这样考虑结果肯定是一样的。**每一处需要挖去的高度**可以计算存储入**数组**：\[3, 2, 3, 1, 2, 3, 2, 0, 1, 2, 1, 2\]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

我们最开始将施工天数设定为第一块需要挖去的高度。如上图 days = 3。

接着，我们第二块开始，从左至右依次考虑：

*  **如果当前需要挖去的高度比前一块低**，那么这一块的施工时间可以在之前一并完成（每一天挖土机可以将连续一段区间挖掉一格土），我们在当前这一块**不需要加时**。
 *  **如果当前需要挖去的高度比前一天高**，那么我们**需要加时**，days += 两者高度差。

比如上面的用例，我们的算法过程如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2][]

方法很简单，就是这个思维方式很难想到。代码也没啥难度，直接上代码了：

哦对，记得把数据类型都用 long long int，不然可能由于数字溢出而 wa...

#include <stdio.h>
    
    #define LEN 100005
    
    long long h[LEN];  //每一处需要挖去的高度
    
    int main() {
        long long wid, height;
        scanf("%lld %lld", &wid, &height);
    
        for(long long i = 0; i < wid; i++) {
            long long cur;
            scanf("%lld", &cur);  //输入最终要求的高度
            h[i] = height - cur;  //计算每一处需要挖去的高度
        }
    
        long long ans = h[0];  //初始天数
        for(long long i = 1; i < wid; i++) {
            if(h[i] > h[i - 1]) 
                ans += h[i] - h[i - 1];  //加时
        }
    
        printf("%lld\n", ans);
    }

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

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

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

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

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

[h]: https://img-service.csdnimg.cn/img_convert/8ba38909d7b934b4ef82fc0a750aec2a.png
[h 1]: http://lexue.bit.edu.cn/filter/tex/displaytex.php?texexp=%20h%20
[h_3]: https://img-service.csdnimg.cn/img_convert/daec868495a57275c4d4ab5b6fb09e87.png
[h_3_h_3]: http://lexue.bit.edu.cn/filter/tex/displaytex.php?texexp=%20h%3D3%20
[20200909085024269.png]: /images/20221123/fa9e8e6bce6740168bb2d6e30b0501d4.png
[20200909085024262.png]: /images/20221123/e173f2da0ba24abc9c9d4c51d6f43b31.png
[n_1 _leq n _leq 100000 _h_1 _leq h _leq 1000000]: https://img-service.csdnimg.cn/img_convert/9148d01375d3158ebd4524d6ce216807.png
[n_1 _leq n _leq 100000 _h_1 _leq h _leq 1000000 _n_1 _leq n _leq 100000 _h_1 _leq h _leq 1000000]: /images/20221123/dd82c8c87a2c49c18ff719e9c356607d.png
[n]: https://img-service.csdnimg.cn/img_convert/8490b53aabfe83a484fbc712748663d5.png
[n 1]: http://lexue.bit.edu.cn/filter/tex/displaytex.php?texexp=%20n%20
[a_i _0 _leq a_i _leq h]: https://img-service.csdnimg.cn/img_convert/68cf89e279533cd1dc886588f26d3a92.png
[a_i _0 _leq a_i _leq h _a_i _0 _leq a_i _leq h]: http://lexue.bit.edu.cn/filter/tex/displaytex.php?texexp=%20a_i%20%280%20%5Cleq%20a_i%20%5Cleq%20h%20%29%20
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/32fcf60508b1449597e93d8725faa513.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20221123/27dcf7eda23a448a976abe0ad66b520f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: /images/20221123/8e1bb33f98d74bd2be728b53e3291ef4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]: /images/20221123/10a63b5457f142fc8d50c083703f4083.png