Mr.K 018 发布于四月 14, 2020 分享 发布于四月 14, 2020 (已修改) · 只看该作者 第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修改 注释 摸鱼奇才咖啡喵 295.00节操 次海鲜大刺身~ 2 链接到点评
yhz012 发布于四月 14, 2020 分享 发布于四月 14, 2020 (已修改) · 只看该作者 等下我昨天的传送门还稍微有点问题呢(x 感觉是组合数学的问题 最平凡解是你有多少数字我用多少栈,然后一个数字一个栈 但是很显然的是,对于数字1我们不需要栈,因为直接把1丢出来就好了 同样地,我们因此可以发现,跟在1后面的+1序列全都不需要栈,直接丢出来就可以了 四月 14, 2020,由yhz012修改 链接到点评
Mr.K 018 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 刚刚, yhz012 说道: 等下我昨天的传送门还稍微有点问题呢(x 感觉是组合数学的问题…… 小声说 传送门那个题不用管了,那个是我记错了,本来想出成单向的,可是出题的时候脑抽觉得单双向一样 今天这个题不是难题哦 链接到点评
yhz012 发布于四月 14, 2020 分享 发布于四月 14, 2020 · 只看该作者 9 分钟前, Mr.K 018 说道: 小声说 传送门那个题不用管了,那个是我记错了,本来想出成单向的,可是出题的时候脑抽觉得单双向一样 今天这个题不是难题哦 传送门其实还是能做的 首先如果所有传送门之间没有交叉情况(可以真包含),那么必然是单向的,用单向带走就可以了 麻烦的是传送门之间有交叉 但是这个情况也可以用马尔科夫决策过程来做,暴力policy iteration或者value iteration肯定能converge的,这样每个传送门的选择也就确定单向了 所以说昨天那问题是真的我的老本行了(笑 等我有时间可以写着玩玩 链接到点评
NianRuoshui 发布于四月 14, 2020 分享 发布于四月 14, 2020 · 只看该作者 栈排序不是两个栈就能排了吗 难道有什么我没看懂 NianRuoshui在偷偷前往歌姬住处要签名的时候偶然碰到了管家123,被罚款-2节操 链接到点评
Mr.K 018 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 7 分钟前, NianRuoshui 说道: 栈排序不是两个栈就能排了吗 难道有什么我没看懂 “最少需要多少个栈” 你已经接近正确答案了 Mr.K 018不吃不喝三天三夜只为“汉化”某悬赏游戏,搞定后发现居然是要翻译成俄语.-2节操 链接到点评
卡泽 发布于四月 14, 2020 分享 发布于四月 14, 2020 · 只看该作者 用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 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 29 分钟前, NianRuoshui 说道: 栈排序不是两个栈就能排了吗 4 分钟前, 卡泽 说道: 用3个栈的普适方法 各位注意这句话: 1 小时前, Mr.K 018 说道: 需要说明的是,不同的输入序列需要用到的最小栈数可能是不同的,请对每个输入序列分别计算。 链接到点评
卡泽 发布于四月 14, 2020 分享 发布于四月 14, 2020 · 只看该作者 感觉题目的例子有点奇怪?输入是: 5 4 5 1 2 3 那么怎么先压入3再压入2呢?还是这里写错了? 链接到点评
Mr.K 018 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 1 分钟前, 卡泽 说道: 感觉题目的例子有点奇怪?输入是: 5 4 5 1 2 3 那么怎么先压入3再压入2呢?还是这里写错了? 抱歉写错了,数据应该是4 5 1 3 2,马上改 Mr.K 018在新手区仔细阅读版规时,意外收到来自小小坛娘奖励的4节操。 链接到点评
Mr.K 018 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 10 分钟前, 卡泽 说道: 两个栈和O(logn)的算法我再想想 你会发现这个题其实不关心排序算法的复杂度,只要能让栈的数量少一点,O(n!)都是无所谓的,因为反正也不是真的排序嘛( 链接到点评
卡泽 发布于四月 14, 2020 分享 发布于四月 14, 2020 · 只看该作者 我有点没有理解题目的意思。。 按我目前的理解: 如果输入已经排好序了,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 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 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 发布于四月 14, 2020 分享 发布于四月 14, 2020 (已修改) · 只看该作者 车队入库嘛……2个栈 栈1姑且叫连续栈 栈2叫临时栈好了 需要记录2个值 连续栈的最大值和最小值 初始值为0 然后记录当前已处理的值 初始为0 对每一个输入值 判断是不是已处理值+1 如果是则输出 不需要过栈 然后更新已处理值 同时判断连续栈是否可以清空 即已处理值是否等于连续栈最小值+1 如果需要入中转栈 那么判断是不是可以直接入连续栈 即是否等于连续栈最小值-1 或者连续栈为空 如果不能则需要启用临时栈 临时栈的逻辑稍微麻烦一点 要借用连续栈保证临时栈里的元素是逆序的 具体伪代码略 不过反正你问的是需要几个栈…… 稍微想了一下好像不需要连续栈的最大值……那个本来是用来合并连续栈的 但是反正合并的时候也要用到第二个栈 四月 14, 2020,由ppzt修改 ppzt在诱导萌新女装时被路过的随便拦下,被批评教育并收取学费-3节操 链接到点评
Mr.K 018 发布于四月 14, 2020 作者 分享 发布于四月 14, 2020 · 只看该作者 2 小时前, ppzt 说道: 车队入库嘛……2个栈 栈1姑且叫连续栈 栈2叫临时栈好了 需要记录2个值 连续栈的最大值和最小值 初始值为0 然后记录当前已处理的值 初始为0 对每一个输入值 判断是不是已处理值+1 如果是则输出 不需要过栈 然后更新已处理值 同时判断连续栈是否可以清空 即已处理值是否等于连续栈最小值+1 如果需要入中转栈 那么判断是不是可以直接入连续栈 即是否等于连续栈最小值-1 或者连续栈为空 如果不能则需要启用临时栈 临时栈的逻辑稍微麻烦一点 要借用连续栈保证临时栈里的元素是逆序的 具体伪代码略 不过反正你问的是需要几个栈…… 稍微想了一下好像不需要连续栈的最大值……那个本来是用来合并连续栈的 但是反正合并的时候也要用到第二个栈 陷阱受害者+1 有一说一 我特意提了一句不同输入序列结果会不同的来着 想想看,什么情况下一个栈就行呢?这才是本题的第二个关键 链接到点评
ppzt 发布于四月 14, 2020 分享 发布于四月 14, 2020 · 只看该作者 6 小时前, Mr.K 018 说道: 陷阱受害者+1 有一说一 我特意提了一句不同输入序列结果会不同的来着 想想看,什么情况下一个栈就行呢?这才是本题的第二个关键 我说了啊……啥时候需要启用顺序栈 啥时候需要启用临时栈 链接到点评
推荐贴