题解：CF1998C Perform Operations to Maximize Score

Floze3 Mess
  2024-08-11 18:15:01 2024-08-11 18:15:01 创建   2024-08-11 18:16:31 2024-08-11 18:16:31 更新    195 字  1 分钟  

传送门

思路简介

做过的最难的Div2 C

显而易见的，如果我们选择出的那个数可以被增加，那么增加那个数一定更优。这启示我们分两种情况考虑：一种是选出能被增加的数中的最大的数，并且一直增加那个数；另一种是选出不能被增加的数中的最大的数，并且增大中位数。第一种情况是好处理的，如何处理第二种情况？我们考虑要是中位数为某个特定的值所需的最少操作次数具有单调性，我们不妨考虑二分中位数，可以做到check。单组数据的时间复杂度为。

代码

赛时提交链接

  • 标题: 题解：CF1998C Perform Operations to Maximize Score
  • 作者: Floze3
  • 创建于 : 2024-08-11 18:15:01
  • 更新于 : 2024-08-11 18:16:31
  • 链接: https://floze3.github.io/2024/08/11/cf1998c-solution/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
题解：CF1998C Perform Operations to Maximize Score
  1. 思路简介
  2. 代码