What is the most stressful aspect of the CF1132D training program?

本文共计1364个文字，预计阅读时间需要6分钟。

题目链接+题目+链接：题解方法一+知识点：贪心，优先队列，二分。题解方法二+知识点：自然，二分。显然，这道题可以用二分解答。check函数可以使用小根堆，维持时间最短的先充电。但优化这道题会炸。

题目链接

题目

见链接。

题解 方法一

知识点：贪心，优先队列，二分。

显然，这道题可以用二分答案做。check 函数可以用小根堆，让维持时间最小的先充电。

但是不优化这道题会炸。有两个关键优化：一个是快读快写能省不少时间，还有一个是把维持天数当一个变量存起来以免重复运算浪费时间。其他一些小优化：用 pop 把元素弹出代替析构函数自己初始化能省一点时间，只让天数小于 \(k\) 的电脑入队，每次充完电检测维持天数小于 \(k\) 的才重新入队。优化前是超 \(3\) 秒限制的，优化后是 \(1.5\) 秒还算可以。

时间复杂度 \(O((n+k)\log n)\) ，常数应该在 \((100,1000)\)

空间复杂度 \(O(n)\)

方法二

知识点：贪心，二分。