填坑Ⅱ | 简单的数据结构

本是古典何须时尚 2022-12-08 06:33 127阅读 0赞

> ## 20. 填坑Ⅱ ##
> 
> <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**
> 
> emmm，还是北湖深坑，不用惊喜，不用意外。
> 
> 我们继续用石头填！北湖的地面依旧是一维的，每一块宽度都为1，高度是非负整数，用一个数组来表示。
> 
> 还是提供不限量的1x2规格的石头。但是这一次是 Dark来填坑，他有很强烈的强迫症，所有的石头只能水平摆放（宽为2，高为1）。问这样是否可以将北湖填平。（所有地面到达同一高度即为填平）
> 
> **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>NO↵</li> 
>      <li>NO↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

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

emmmm我总觉得个填坑Ⅱ和Ⅰ反了，但是怎么今年依旧还是这个顺序....相信看懂Ⅰ的朋友这个Ⅱ真的小菜一碟！

第一题的传送门，请看懂第一题再来看第二题：[填坑Ⅰ | 简单的数据结构][Link 1]

既然不可以以1为底2为高去填，那么与第一题的思路差别就是：

1.  最后的结果判定为yes的条件：栈**最后为空** 或 栈内剩余的**唯一元素必须是最高点**（好好想想这是为啥）
2.  我们**不可以对坑进行预处理**（将他们尽可能填到最高处），我们直接讨论之后的情况。情况变得非常简单：**入栈的不是01，而是它们本身的高度！**

依次讨论每一个初始高度，**如果相邻的同高且两侧都比它们俩低，那么可以消去忽略不计**。如果最后序列里有超过一个元素或剩余的唯一元素不是最高点，则输出NO！如果在讨论的过程中，栈顶元素比栈内高，那我们可以不必继续讨论....

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

你们可以多画一些测试用例来理解如上思路，鸡翅能力有限(两点了，该睡会了)说不太明白，上面都是精华，剩下的就交给大家了~

附上完整ac代码：

#include<cstdio>
    #include<cstring>
    #include<stack>
    
    using namespace std;
    
    long long int a[200010] = {0};
    stack<int> stk;   //定义一个栈
    
    int main() {
        long long int n;
    
        //当存在输入的时候
        while (scanf("%lld", &n) != EOF) {
            memset(a, 0, sizeof(a[0]));   //将数组初始化为 0
            while (!stk.empty())  //清空栈
                stk.pop();
    
            long long maxHeight = 0;
            for (long long i = 0; i < n; i++) {
                scanf("%lld", &a[i]);
                //记下最高值
                if (a[i] > maxHeight)
                    maxHeight = a[i];
            }
    
            for (long long i = 0; i < n; i++) {
                if (!stk.empty() && a[i] == stk.top())  //栈非空且可以对应时
                    stk.pop();
                else {   //不可以消去
                    if (!stk.empty() && stk.top() < a[i])   //如果比前一个高
                        break;
                    else
                        stk.push(a[i]);
                }
            }
    
            long long remainCount = stk.size();
            if (!remainCount)
                printf("YES\n");
            else if (remainCount == 1 && stk.top() == maxHeight)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

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

### End ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

[Link 1]: https://blog.csdn.net/weixin_43787043/article/details/108675129
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/8c6392e5492e46e6aa56ba2305e74576.png