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

AT_arc154_d [ARC154D] A + B C ?

直接被这个题闪到了。

首先发现 \(1\) 是最小的,其有很多性质,因此可以花费 \(n - 1\) 次操作比较出来 \(1\) 的位置。

同理,\(2, 3, ..., n\) 都是可以这样比较出来的,但操作次数是 \(O(n^2)\) 级别的,题目只给了我们 \(O(n \log n)\) 次操作。

注意到 \(p_i + 1 > p_j \to p_i \ge p_j\),也就是我们可以通过一次操作比较两个数的关系,这显然可以用归并排序等理论信息论比较在 \(O(n \log n)\) 级别的排序算法解决该问题。

http://www.hskmm.com/?act=detail&tid=17245

相关文章:

  • SQL注入-联合注入
  • JVM对象创建与内存分配
  • 目录
  • 交互:在终端中输入用户信息
  • 电脑迁移技巧:适用于 Windows 10/11 的免费磁盘克隆优秀的工具
  • Java学习日记9.18
  • 一种CDN动态加速首次访问加速方法
  • 9.25
  • 字典
  • CF1716题解
  • 使用vosk模型进行语音识别
  • AI Agent如何重塑人力资源管理?易路iBuilder平台实战案例深度解析
  • docker-compose + macvlan + Elasticsearch - 9.1.4 + Kibana - 9.1.4
  • WinForm 计时器 Timer 学习笔记
  • RocketMQ入门:基本概念、安装、本地部署与集群部署 - 详解
  • 【LeetCode】122. 买卖股票的最佳时机 II
  • VSCode 使用技巧笔记
  • 【LeetCode】55. 跳跃游戏
  • Ansible + Docker 部署 Apache Kafka 3.9 集群
  • 【LeetCode】45. 跳跃游戏 II
  • 深入了解一波JVM内存模型
  • 什么是UDFScript用户自定义脚本
  • 【LeetCode】121. 买卖股票的最佳时机
  • CCPC2024-Zhengzhou G Same Sum(线段树)
  • Openwrt-DDNS 配置详解
  • 实用指南:Metal - 2. 3D 模型深度解析
  • 【2025.9.16】关于举办PostgreSQL数据库管理人才研修与评测班的通知
  • Java锁相关问题
  • CDN中使用边缘函数实现自定义编程
  • 第一次课程中的所有动手动脑的问题以及课后实验性的问题