美团 · 模拟 · 算法编程题
美团 模拟 N ≤ 1e5 时限 1 秒 / 256 MB

题目描述

小美有N张牌，牌上分别写有数字1到N，她打算用这些牌和小团玩洗牌游戏。小美将牌叠成一堆放在桌上，每次可以从桌上的牌堆的顶部取走一张牌，叠放在自己手上，或者将自己手上的牌堆的顶部或底部的一张牌交给小团，直到N张牌都交给小团。通俗地说，一开始桌上的牌堆有N张牌，小美手上的牌堆有0张牌，她每次可以将桌上牌堆顶的一张牌放到自己手上的牌堆顶，或者将手上牌堆顶或牌堆底的一张牌交给小团。小团收到的牌上面的数字（按收到的顺序）依次为A[1]到A[N]。现在，小美问小团是否有可能，初始时桌上的牌堆从顶部到底部，牌上所写的数字依次为1到N。

输入输出

输入描述
第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；
第二行输入N个由空格隔开的整数，表示A[1]到A[N]（保证是1到N的一个排列）。
输出描述
每组数据输出占一行，如果初始时桌上的牌堆从顶部到底部，牌上所写的数字依次为1到N是有可能的，则输出“Yes”，否则输出“No”（均不包括引号）。

样例共 1 组

样例 1 · 对于第一组数据，假设初始时桌上的牌堆从顶部到底部，牌上所写的数字依次为1到5，小美先从桌上依次取走写有数字1到3的牌，再将牌堆顶和牌堆底写有数字3和1的牌依次交给小团，接着从桌上依次取走写有数字4和5的牌，然后将牌堆顶和牌堆底写有数字5和2的牌依次交给小团，最后将仅剩的写有数字4的牌交给小团，那么小团收到的牌上面的数字就依次为3、1、5、2、4。
输入
2
5
3 1 5 2 4
5
3 5 2 1 4
输出
Yes
No

算法解析依据充分

考点：模拟

数据规模 N ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e5，T ≤ 10
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：模拟

本题切入点

正向模拟难判定，倒着做：从最终序列出发，用双端队列还原桌面牌堆的取牌过程，最后检查是否为 1..N。

不涉及复杂算法，把题目描述的流程原样翻译成代码逐步执行即可。

思路框架（模拟 通法 · 非本题专属）

  1. 用变量记录题目要求的「状态」（当前值、剩余数量、当前位置等）。
  2. 按题面给出的顺序，把每一步操作写成一段代码，逐条执行。
  3. 每一步执行后更新状态，并在题目要求的位置输出或累计答案。
  4. 注意循环的边界：执行多少次、何时终止、是否能终止。

实现要点：结构上通常是一个外层循环包住若干 if/else 分支；只要状态定义清楚，正确率很高。

复杂度：时间 O(操作次数) ｜ 空间 O(状态数)

该范式的通法易错点

  • 终止条件写错导致死循环或漏做最后一次操作。
  • 状态更新顺序颠倒（先改了下标又用旧下标）。
  • 题目里「最多 / 恰好 / 至少」的语义差别没区分。

对照本题

  • 数据规模 N ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。

样例解读

样例 1：输入 2 / 5 / 3 1 5 2 4 / 5 / 3 5 2 1 4 → 输出 Yes / No

对于第一组数据，假设初始时桌上的牌堆从顶部到底部，牌上所写的数字依次为1到5，小美先从桌上依次取走写有数字1到3的牌，再将牌堆顶和牌堆底写有数字3和1的牌依次交给小团，接着从桌上依次取走写有数字4和5的牌，然后将牌堆顶和牌堆底写有数字5和2的牌依次交给小团，最后将仅剩的写有数字4的牌交给小团，那么小团收到的牌上面的数字就依次为3、1、5、2、4。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：美团2023校招笔试-编程题（算法编程题）。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解