本题的核心是模拟一个栈(暂存箱)的操作过程,以恰好留下指定的目标包裹序列。由于暂存箱具有后进先出的特性,最终保留的包裹从底到顶的顺序恰好对应目标序列从左到右的顺序。为了保证操作合法,我们可以按照目标序列从底到顶的顺序(即输入顺序)依次“定格”每一个目标包裹。
算法步骤:
next,表示下一个即将从传送带取下的包裹编号,初始为 1。next <= x,说明当前队首包裹编号还没有超过目标 x,需要将 next 从传送带上取下并放入暂存箱,因此输出一条 In 指令。在一个自动化包裹分拣系统中,有一批编号为 1 到 n 的待处理包裹,它们按编号顺序排列在传送带上。操作员可以对最前面的包裹执行两种操作:
In:将当前最前面的包裹从传送带上取下,放入一个暂存箱。暂存箱具有后进先出的特性,即每次只能看到和取出最顶部的一个包裹。Out:将暂存箱最顶部的包裹取出并丢弃。初始时暂存箱为空。现给定一个目标包裹序列,表示操作结束后希望暂存箱中保留的包裹从底到顶的顺序。多余包裹必须在操作过程中通过 Out 丢弃。请你输出一个合法的操作序列(以逗号分隔的指令串),使得最终暂存箱中的包裹序列恰好与给定的目标序列一致。
保证待处理包裹总数 n 和目标保留包裹数量 m 均不超过 100,且输入保证存在合法的指令序列。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册