当前位置: 首页 > news >正文

111111

k k k 只有 2 n − 1 , 2 n − 2 2n-1,2n-2 2n1,2n2 两种取值,如果 k = 2 n − 2 k=2n-2 k=2n2,即 2 ( n − 1 ) 2(n-1) 2(n1),那么我们可以拿出 n − 1 n-1 n1 个栈来放数,最后留一个栈(称其为特殊栈)来消除底部的数,容易证明这样肯定可以得到合法方案。

再看 k = 2 n − 1 k=2n-1 k=2n1,这样会出现 2 n − 2 2n-2 2n2 个数放完了,还有一个多出来的数,考虑这个数的归宿。

设多出来的数为 w w w,我们找到在它之后的最先出现在某个栈的底部的数 u u u,设 u u u 所在栈为 x x x,该栈栈顶为 v v v,进行分讨。

  • w w w u u u 先出现,那么我们将 w w w 放入特殊栈,因为之后用不到 2 2 2 操作。
  • 否则比较 u , v u,v u,v,若 u u u v v v 先出现,那么之后需要借用特殊栈消除 u u u,所以 w w w 放到 x x x 栈顶。
  • 否则就是 v < u < w v<u<w v<u<w,我们将 w w w 放入特殊栈,之后会出现 v , u v,u v,u 依次被消除的情况,此时 x x x 又空了,所以我们将 x x x 设为新的特殊栈。

本题实现细节较多,简单说一下:

  • 记录每个数所在栈。
  • 用队列来维护当前有哪些空栈,注意某个数出栈时,该栈有空余位置后要重新入队。
  • 1 , 2 1,2 1,2 操作分别写成函数,方便维护。

最后还有一个时间复杂度的问题,我们找 u , v u,v u,v 的出现顺序时,能否暴力往后找?答案是可以的,因为只有出现所有非特殊栈放满后,才会去找,而下一次再出现这种情况的位置,一定不会和之前重合,所以最多只会循环 m m m 次。

时间复杂度 O ( ∑ m ) O(\sum m) O(m)


http://www.mrgr.cn/news/61084.html

相关文章:

  • 【MySQL】 运维篇—备份与恢复:使用mysqldump进行数据库备份与恢复
  • 云生X易搭云 | 打造全流程透明化法务工作平台
  • SpringBoot技术构建的商场应急响应系统
  • DDIM扩散模型的加速采样(去噪)算法 Denoising Diffusion Implicit Models
  • 商场应急决策支持系统:SpringBoot技术解析
  • 【单机游戏】大富翁游戏攻略
  • Redis-概念、安装、基本配置
  • Docker-在Centos中部署Shell脚本获取镜像并构建容器
  • Vue.js组件开发【基础开发步骤 + 实践】
  • SQL类型转换
  • ssm006基于java的少儿编程网上报名系统(论文+源码)_kaic
  • shodan-5
  • 【Spring面试题】
  • 【linux】fdisk磁盘分区管理
  • RHCE: 例行性工作 at 与 cron
  • Hypermesh如何批量重命名component
  • MNIST 数据集的CSV的格式的使用(ANN)
  • Linux信号
  • CSP-J2024入门级T3:小木棍
  • 大白话讲解Spring对数据源和事务管理以及多数据源配置