转跳到内容

每 日 算 法 挑 战 【第5期】


推荐贴

第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)*的。
可以把栈想象成一个装鞋盒的筒子。这个筒子很细,鞋盒只能放一排,因此每次只能取走最顶上的鞋盒,也只能把新的鞋盒放在最顶上。不过,倒是可以认为这个筒子很长,可以装很多很多鞋盒。

GxJbM4.png

图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输出,结束。

,由Mr.K 018修改
注释
摸鱼奇才咖啡喵 摸鱼奇才咖啡喵 295.00节操 次海鲜大刺身~
链接到点评

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

感觉是组合数学的问题

 

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

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

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

,由yhz012修改
链接到点评
9 分钟前, Mr.K 018 说道:

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

今天这个题不是难题哦

传送门其实还是能做的

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

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

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

 

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

等我有时间可以写着玩玩

链接到点评

用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)的算法我再想想

 

链接到点评
29 分钟前, NianRuoshui 说道:

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

 

4 分钟前, 卡泽 说道:

用3个栈的普适方法

各位注意这句话:

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

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

 

链接到点评

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

按我目前的理解:

如果输入已经排好序了,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一下。

链接到点评
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+的糖

链接到点评

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

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

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

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

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

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

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

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

 

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

 

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

,由ppzt修改

ppzt在诱导萌新女装时被路过的随便拦下,被批评教育并收取学费-3节操

链接到点评
2 小时前, ppzt 说道:

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

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

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

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

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

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

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

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

 

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

 

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

陷阱受害者+1

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

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

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款