填坑Ⅰ | 简单的数据结构

Dear 丶 2022-12-08 06:04 121阅读 0赞

> ## 19. 填坑Ⅰ ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年09月17日 星期四 12:00</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年09月24日 星期四 12:00</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年10月10日 星期六 23:00</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **Description**
> 
> 又是北湖深坑，惊不惊喜，意不意外？！
> 
> Rack觉得用水填湖太没意思了，用石头填坑多有意思。假设北湖的地面还是一维的，每一块宽度都为1，高度是非负整数，用一个数组来表示。现提供不限量的1x2规格的石头，问是否可以将北湖填平。（所有地面到达同一高度即为填平）
> 
> 注：石头只能水平或垂直填放。
> 
> **Input**
> 
> 样例有多组输入至文件末尾；每组用例占两行；
> 
> 第一行输入1个整数n表示北湖地面总宽度；
> 
> 第二行输入n个整数用空格间隔，表示地面高度。
> 
> **Output**
> 
> 若能填平则输出“YES”，否则输出“NO”。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td> 
>     <ol> 
>      <li>5↵</li> 
>      <li>2&nbsp;1&nbsp;1&nbsp;2&nbsp;5↵</li> 
>      <li>3↵</li> 
>      <li>4&nbsp;5&nbsp;3↵</li> 
>      <li>3↵</li> 
>      <li>1&nbsp;2&nbsp;3↵</li> 
>     </ol></td> 
>    <td> 
>     <ol> 
>      <li>YES↵</li> 
>      <li>YES↵</li> 
>      <li>NO↵</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][]

**2、它的使用**  
      注意，小学期你直接学会c++封装的STL的使用即可，至于它是怎么实现的，下学期数据结构这门课有你学的。

#include <stack>  //导入库
    using namespace std;  //确定命名空间
    
    stack<int>  s;  //定义一个元素是整型的栈，命名为s
    
    int a;
    s.push(a);   //将整型变量压入栈顶
    
    s.size();   //返回栈内元素个数
    
    s.empty();  //返回栈是否为空
    
    /* 注意，以下的操作必须先保证栈不为空，否则会re */
    
    int b = s.top();  //查看栈顶元素，存入变量b中
    
    s.pop();  //出栈：栈顶元素弹出（注意，这个函数返回值为空）

如果你学有余力，也可以看看鸡翅总结的**栈的数据结构笔记**，贴心传送门：

[Stack | 栈的数组实现][Stack _]

[Stack | 栈实现 —— 后缀表达式][Stack _ _ _]

[Stack | 栈实现 —— 符号配对][Stack _ _ _ 1]

### 二、算法分析 ###

下面来分析一下这道题：  
       用1x2的石头填坑，应该这样理解：可以**每次将单位长度升高2米**，或者**可以将连续两个单位长度同时增长1米**。

由于我们最后的目的就填平至任意整数高度。那么**对于两个同高的相邻地方，他们绝对是不会影响我们的结果的**。因为我们可以一米一米地对他俩增高，到任意我们想要的高度。故**两两相同高度的地方我们可以直接忽略！**比如高度1 2 2 3，我们可以直接视为1 3相邻，忽略其中两个。所以**相邻的定义就放大了**。（这里一定要弄明白，这是整个思路的核心，如果不明白就看看后面的再仔细想想）

那么我们的思路就出来了，下面是最清楚的思路，其他方法都可以等价地替换成这个方法的处理。所以以下的方式可以正确地解决判断问题：

**Ⅰ、** 首先找到**最高点**。

**Ⅱ、** 将石头以1为底2为高来使用，我们尽量将每一处升高到最高点处：

*  与最高点相差奇数个高度，可以填至与最高处只相差一米。记为**1**
 *  与最高点相差偶数个高度，可以恰好填至与最高处齐平。记为**0**

**Ⅲ、**然后依次遍历记录下来的整个01串，**有相同的在一起可以两两相消**，如果最后01串内元素大于1，那么说明北湖永远填不平喽！

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

你不能理解的就是为啥可以两两相消吧，看看如下例子（测试用例1：2 1 1 2 5）。我们先让每一列贴近最高点，最后的01串为10010。接着可以消成110，接着可以消成0，所以最后输出YES

认真理解一下2、3列为什么不影响最后的结果，我们可以直接将2、3列抵消掉？你想想我们怎么再在如下基础上填平，想好了你估计能明白，因为2、3它们可以以1为单位配合到任何高度，不影响我们的结果，可以直接忽略！！！这里有点只可意会的感觉，你如果想不通就多想几个用例....

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

### 三、算法实现 ###

你现在应该想到了算法应该怎么实现吧！先找到最高点，然后依次记录每一点与最高点相差高度的奇偶性，奇数记为1，偶数记为0。然后讨论这个01数组...然后得出结果....前面的思路都是对的，而如果你用**数组这个数据结构储存，到最后去处理数组里存储的01串结果，就有点繁琐了**...但是！你有没有想到你没有用到栈诶！有更加简单处理01串的办法！用栈！

你想想栈的特点要怎么应用到这个题里呢！**栈每次只能访问和处理栈顶的元素**，如果我们依次讨论并将相同的0/1消掉，是不是栈就特别合适呢！这么说好抽象，栈这种微妙的作用，你仔细看看例子来理解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2][]

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

好了，下面给出完整AC代码：

不对，再另外提几嘴。别嫌我啰嗦，说不定给你减少几小时debug的时间。

**1、scanf返回值的问题**

不知道你有没有注意过，乐学提交题目经常会给你返回这样一个warning。（虽然我们程序员经常忽略warning只在乎error）

![20200919010450111.png][]

这就是字面意思，你**忽略了scanf函数的返回值！**什么？我用了这么久的scanf函数还有返回值！？我从来没有用过啊，它不是输入的吗！可是你可能忘了c里所有函数都有设定返回值（void为空）。从这里我们可以看到scanf返回值为int类型。什么意思呢？这个会返回一个是否成功输入的标识，具体的我就不说了。**当 c 在处理输入时，一一读取文件内容，当每有可以读取的时候，scanf的返回值就是EOF**。 EOF是一个C标准库定义的常量，不知道你是否还依稀记得 C 语言里把常量用大写字母来标识。(就比如下面代码我就定义了一个常量MAXN，只不过是宏定义的形式哈...)

**2、循环输入必须注意**

这道题又是循环处理输入的一个题，很多朋友会先写出一般的处理代码再套上循环。或许你也苦恼过为啥我运行过没有问题呀，再次运行就不对了呢？这种的**多样例测试一定要注意，如果你没有在每次循环前将变量都初始化，你很有可能后面一直在反复在之前的基础上使用变量！**最好的检测方式就是输入两次一样的用例，看看结果是否相同，如果不同，那么恭喜你中招了！

所以**每定义一个变量就对它初始化这是一个很棒的编程习惯。**基本数据类型比如int，double之类的我就不说了，数组我们通常用string.h或cstring类中的memset函数进行初始化，栈我们一般在使用前要初始化为空！

这里的易错点就是，你没有每次把栈清空！！后面的运行就会以上一次栈内剩余元素打底。

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

#include<cstdio>
    #include<cstring>
    #include<stack>
    
    using namespace std;
    
    #define MAXN 200010
    
    long long int a[MAXN] = {0};
    stack<int> stk;
    
    int main() {
        long long int n;
    
        //当输入没有中止的时候，读入 n
        while (EOF != scanf("%lld", &n)) {
    
            /* 初始化 */
            int maxElement_index = 0;  //记录对高点的下标
            memset(a, 0, sizeof(a[0]));   //将数组a全都赋值为 0
            while (!stk.empty())  //清空栈
                stk.pop();
    
            /* 处理输入 */
            for (int i = 1; i <= n; i++) {
                scanf("%lld", &a[i]);
                //找出最高点下标
                if (a[i] > a[maxElement_index])
                    maxElement_index = i;
            }
    
            /* 核心算法部分 */
            int temp;
            for (int i = 1; i <= n; i++) {
                if ((a[maxElement_index] - a[i]) % 2 == 1) //差的高为奇数
                    temp = 0;
                else  //差的高为偶数
                    temp = 1;
    
                if (!stk.empty() && temp == stk.top())  //栈非空的前提下：与前一个可以对应相消时
                    stk.pop();
                else
                    stk.push(temp);
            }
    
            /* 处理结果 */
            int remainCount = stk.size();   //计算栈内剩余元素
            if (remainCount <= 1)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

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

### End ###

欢迎关注个人公众号“鸡翅编程”，这里是认真且乖巧的码农一枚，旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/ef648696030d4f06b81fa9f70fb4a240.png
[Stack _]: https://blog.csdn.net/weixin_43787043/article/details/103937989
[Stack _ _ _]: https://blog.csdn.net/weixin_43787043/article/details/103939370
[Stack _ _ _ 1]: https://blog.csdn.net/weixin_43787043/article/details/103939040
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20221123/5c1b9ffacf9f44618b3858204845ed01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: /images/20221123/a3dce2aee35d4cb5b609c62f92c47df2.png
[20200919010450111.png]: /images/20221123/d31fde4b4c6b4fdc8ec8041490f89a73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 3]: /images/20221123/05e7859f11294f3a8b640778fcfec50f.png