娱乐 每 日 算 法 挑 战 【第5期】

[Mr.K 018]

第5期来啦！

这道题看上去没什么头绪，但其实没有那么难哦！

前排召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui

第5期 简单的排序题

Mr.K 018: 现在有一列数，从1到n，是乱序排列的，要对它排序。
Mr.K 019: 听上去不复杂啊，然后呢？
Mr.K 018: 你能使用的数据结构只有栈。队列啊，数组啊，堆啊什么的都不许用，只有栈。
Mr.K 019: 你等一下，栈是个啥？

插入科普：栈是个啥？
摘自百度百科：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。就是说，一个栈是*后进先出(Last In First Out, LIFO)*的。
可以把栈想象成一个装鞋盒的筒子。这个筒子很细，鞋盒只能放一排，因此每次只能取走最顶上的鞋盒，也只能把新的鞋盒放在最顶上。不过，倒是可以认为这个筒子很长，可以装很多很多鞋盒。

图5-1 堆栈及其操作示意

好的，我们继续。

 

Mr.K 018: 除此之外，我希望你用尽可能少的栈就完成这个任务。能用一个就不用两个。
Mr.K 019: 可是我根本不需要用栈啊，直接一口气把1到n输出不就完了么？
Mr.K 018: 呃不是的，这里其实是把一个其他什么数据元素表示成数字了。本来那个东西没准是份名单啊什么的，数字其实就是个id。不过那不重要。
Mr.K 018: 简单说，直接输出是不行的，必须排好序之后输出本来的那个东西才行。不过，输出了之后，那个数就可以不管了。
Mr.K 019: 啊，这……那我不会（直球
Mr.K 018: 我早就知道你不会，那降低一点要求吧。我给你这一列的数，你告诉我最少用几个栈就行，剩下的事情我来办。
Mr.K 019: 啊，这……

就算018已经降低了要求，019好像也还是不太会。现在他把这个问题抛给了各位，相信同盟的各位肯定能解决这个问题。

需要说明的是，不同的输入序列需要用到的最小栈数可能是不同的，请对每个输入序列分别计算。

输入

有多组测试用例，请读取到文件尾。

每组测试用例由两行组成。第一行是一个正整数n，满足1<=n<=10^5；第二行是一个1到n的排列，保证1到n的每个数都刚好出现一次。

输出

每个测试用例输出一行一个整数，表示对这n个数进行排序最少需要多少个栈。

样例输入

5
4 5 1 3 2

样例输出

2

输出解释

可以先把前三个数压入栈1，随后弹出栈1顶端的1.之后把3和2压入栈1后，依次弹出栈1顶端的2和3输出。此时，栈1中有4 5，栈2为空。将栈1顶端的5弹出并压入栈2，就可以弹出栈1顶端的4输出。再弹出栈2顶端的5输出，结束。

四月 14, 2020，由Mr.K 018修改

[yhz012]

等下我昨天的传送门还稍微有点问题呢（x

感觉是组合数学的问题

 

最平凡解是你有多少数字我用多少栈，然后一个数字一个栈

但是很显然的是，对于数字1我们不需要栈，因为直接把1丢出来就好了

同样地，我们因此可以发现，跟在1后面的+1序列全都不需要栈，直接丢出来就可以了

四月 14, 2020，由yhz012修改

[Mr.K 018]

刚刚, yhz012 说道:

等下我昨天的传送门还稍微有点问题呢（x

感觉是组合数学的问题……

小声说 传送门那个题不用管了，那个是我记错了，本来想出成单向的，可是出题的时候脑抽觉得单双向一样

今天这个题不是难题哦

[yhz012]

9 分钟前, Mr.K 018 说道:

小声说 传送门那个题不用管了，那个是我记错了，本来想出成单向的，可是出题的时候脑抽觉得单双向一样

今天这个题不是难题哦

传送门其实还是能做的

首先如果所有传送门之间没有交叉情况（可以真包含），那么必然是单向的，用单向带走就可以了

麻烦的是传送门之间有交叉

但是这个情况也可以用马尔科夫决策过程来做，暴力policy iteration或者value iteration肯定能converge的，这样每个传送门的选择也就确定单向了

 

所以说昨天那问题是真的我的老本行了（笑

等我有时间可以写着玩玩

[NianRuoshui]

栈排序不是两个栈就能排了吗 难道有什么我没看懂

[Mr.K 018]

7 分钟前, NianRuoshui 说道:

栈排序不是两个栈就能排了吗 难道有什么我没看懂

“最少需要多少个栈”

你已经接近正确答案了

[卡泽]

用3个栈的普适方法：将3个栈命名为栈1，栈2，栈max

全压进一个栈1，pop栈1放入栈max。

循环{

pop栈1和max，比较。若栈max pop的更大，则把栈1pop的丢进栈2。反之，将栈max pop的丢进栈2，栈1pop的丢进栈max。（这一步比较了栈1顶和栈max顶的大小，并把小的那个丢进了栈2）

当栈1空时，把栈2全部倒回栈1。

}

最后栈max里就是想要的排序了。这个算法的本质是用3个栈实现了比大小。然后每次把找到的最大元放进一个栈里。时间复杂度O(n^2)。很trivial的算法，但提供了上限（最多用3个栈）。两个栈和O(logn)的算法我再想想

 

[Mr.K 018]

29 分钟前, NianRuoshui 说道:

栈排序不是两个栈就能排了吗

 

4 分钟前, 卡泽 说道:

用3个栈的普适方法

各位注意这句话：

1 小时前, Mr.K 018 说道:

需要说明的是，不同的输入序列需要用到的最小栈数可能是不同的，请对每个输入序列分别计算。

 

[卡泽]

感觉题目的例子有点奇怪？输入是：

5
4 5 1 2 3

那么怎么先压入3再压入2呢？还是这里写错了？

[Mr.K 018]

1 分钟前, 卡泽 说道:

感觉题目的例子有点奇怪？输入是：

5
4 5 1 2 3

那么怎么先压入3再压入2呢？还是这里写错了？

抱歉写错了，数据应该是4 5 1 3 2，马上改

[Mr.K 018]

10 分钟前, 卡泽 说道:

两个栈和O(logn)的算法我再想想

你会发现这个题其实不关心排序算法的复杂度，只要能让栈的数量少一点，O(n!)都是无所谓的，因为反正也不是真的排序嘛（

[卡泽]

我有点没有理解题目的意思。。

按我目前的理解：

如果输入已经排好序了，0个栈直接输出即可。

如果输入形如:(3,2,1)(5,4)(8,7,6)(9,10,11)(14,13,12)，即输入可以被分为许多组。每个组内要么正序要么逆序。即：如果某个组之前的所有组包含1-n，且这个组的长度是k，则这个组形如:(n+1,n+2,...n+k)或(n+k,n+k-1,...n+1)。此时用1个栈。

任何其他情况用两个栈：全部倒进一个栈，然后依次从栈1倒进栈2，再从栈2倒进栈1。每次遇到想要的数，就pop一下。

[Mr.K 018]

19 分钟前, 卡泽 说道:

我有点没有理解题目的意思。。

按我目前的理解：

如果输入已经排好序了，0个栈直接输出即可。

如果输入形如:(3,2,1)(5,4)(8,7,6)(9,10,11)(14,13,12)，即输入可以被分为许多组。每个组内要么正序要么逆序。即：如果某个组之前的所有组包含1-n，且这个组的长度是k，则这个组形如:(n+1,n+2,...n+k)或(n+k,n+k-1,...n+1)。此时用1个栈。

任何其他情况用两个栈：全部倒进一个栈，然后依次从栈1倒进栈2，再从栈2倒进栈1。每次遇到想要的数，就pop一下。

没错，就是这个意思。

但是，判断是否能只用一个栈的算法？

我现在不知道为啥评不了分，记一下这里有个50+的糖

[ppzt]

车队入库嘛……2个栈 栈1姑且叫连续栈 栈2叫临时栈好了

需要记录2个值 连续栈的最大值和最小值 初始值为0

然后记录当前已处理的值 初始为0

对每一个输入值 判断是不是已处理值+1 如果是则输出 不需要过栈 然后更新已处理值

同时判断连续栈是否可以清空 即已处理值是否等于连续栈最小值+1

如果需要入中转栈 那么判断是不是可以直接入连续栈 即是否等于连续栈最小值-1 或者连续栈为空

如果不能则需要启用临时栈 

临时栈的逻辑稍微麻烦一点 要借用连续栈保证临时栈里的元素是逆序的 具体伪代码略

 

不过反正你问的是需要几个栈……

 

稍微想了一下好像不需要连续栈的最大值……那个本来是用来合并连续栈的 但是反正合并的时候也要用到第二个栈 

四月 14, 2020，由ppzt修改

[Mr.K 018]

2 小时前, ppzt 说道:

车队入库嘛……2个栈 栈1姑且叫连续栈 栈2叫临时栈好了

需要记录2个值 连续栈的最大值和最小值 初始值为0

然后记录当前已处理的值 初始为0

对每一个输入值 判断是不是已处理值+1 如果是则输出 不需要过栈 然后更新已处理值

同时判断连续栈是否可以清空 即已处理值是否等于连续栈最小值+1

如果需要入中转栈 那么判断是不是可以直接入连续栈 即是否等于连续栈最小值-1 或者连续栈为空

如果不能则需要启用临时栈 

临时栈的逻辑稍微麻烦一点 要借用连续栈保证临时栈里的元素是逆序的 具体伪代码略

 

不过反正你问的是需要几个栈……

 

稍微想了一下好像不需要连续栈的最大值……那个本来是用来合并连续栈的 但是反正合并的时候也要用到第二个栈 

陷阱受害者+1

有一说一 我特意提了一句不同输入序列结果会不同的来着

想想看，什么情况下一个栈就行呢？这才是本题的第二个关键

[ppzt]

6 小时前, Mr.K 018 说道:

陷阱受害者+1

有一说一 我特意提了一句不同输入序列结果会不同的来着

想想看，什么情况下一个栈就行呢？这才是本题的第二个关键

我说了啊……啥时候需要启用顺序栈 啥时候需要启用临时栈