首页 > 栈内取数算法题求助
头像
马亦
编辑于 2021-04-18 10:11
+ 关注

栈内取数算法题求助

最近刷到一道关于栈内取数的算法题,没什么头绪,有没有大佬来指导下😂😂😂


题目描述

在一个栈中有一个1-n的排列(即序列的长度为n, 且1-n中每个元素只出现一次),
现在你需要把元素按照一定顺序取出,因为这是一个栈,你不能直接从中拿走某个元素,
你需要先拿走排在
该元素之前的元素,然后将目标元素取出,再把这个元素之前取出的多余元素按照任意顺序放回,
已知拿出和放回一个元素花费的时间均为1.
如原序列是[1,2,3,4],如果我们要拿出元素3,则需要先把1,2,3拿出然后再将1,2放回,
总耗时是5,当然放回后的顺序可以是[2,1,4],也可以是[1,2,4]。
现在拿出序列的顺序是已知的,请你求出拿出每一个元素的最小时间是多少。例如上面的例子,我第二个
想拿出的元素是2,如果放回序列是[1,2,4],则所需时间是3,如果放回序列是[2,1,4],则所需时间是1.

输入描述
输入第一行仅包含一个正整数,表示序列的长度n(n <= 100000)
接下来一行有n个正整数,是1-n的排列,中间用空格隔开,表示栈中的序列顺序
第三行同样是一个1-n的排列,表示拿出元素的顺序

输出描述
输出包含n行,每行一个整数,表示拿出第i个元素的最小花费时间是多少

样例输入
3
3 1 2
3 2 1

样例输出
1
3
1

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

热门推荐