Luogu6563 [SBCOI2020] 一直在你身旁

题意：有 个物品和一个数 。

第 个物品有一个价格 ，保证 单调不降。

若购买第 个物品，则可以得知命题”“的真假。

求最差情况下，确知 的值至少需要多少代价。

多组数据，，时限 。

---

快 了，来点 吧。

设 为已将 确定在 之内，还需花费的代价。

边界：。

转移： 这样是 的，考虑优化转移。

---

要求转移 ，可是方程中 嵌套，难以分析单调性。

先从 入手，思考 的条件。

不难发现，该问题有包含单调性，即

所以， 单调不减， 单调不增。这样，两者的分界就是单调的。

可以二分查找分界点，这样的复杂度是 。

---

当 不变， 增加时，再次利用包含单调容易证明分界点不会前移。

这样，利用分界点的单调性，可以均摊 找出分界点。

• 的部分。

  由于 和 都单调不降，直接取最左端的 即可。

  其实，若没有 单调的性质，也可以使用单调队列维护。

• 的部分。

  维护区间 ，使用单调队列即可。

为了节省空间，需要按照特定的顺序 ，这样只可以只用一个单调队列。

复杂度 。