题解：CF377E Cookie Clicker
XZhuRen
·
·
题解
除排序外线性做法。
参考了 {l\color{Red} oveJY} 大神的题解：文章链接。
我们发现，有一些工厂一定是不优的：按照 c_{i} 升序（c_{i} 相同按照 v_{i} 降序）排序后，v_{i}<=premax(v) 的一定是可以删除的。
之后我们就得到了一个 c_{i} 和 v_{i} 都严格上升的序列。
现在设函数：
横坐标为**时间** $t$，纵坐标是**金币数** $sum$。
容易发现，我们的操作顺序总是**先取 $\mathbf{c_{i}}$ 小的**，直到钱够了再取大的。
又有**贪心结论**：一个工厂**如果被购买**，则一定在能取用的第一时间（即当前总金币数 $sum \ge c_{i}$ 时）购买启动。
易知 $F(t)$ 是单调递增，且下凸的。
初始时 $F(t)$ 为一条直线 $sum=0$。
有了这个这两个结论，我们可以考虑增量构造函数 $F(t)$。
首先我们从工厂 $1$ 开始，顺序构造（大的一定在后面，以这个基础确定第一次出现的位置）。
每次对于当前的工厂，找到最早的时间 $t$ 使得 $F(t) \ge c_{i}$，这就是本工厂的启动时间，根据贪心结论，这个时间的**固定的**。
再确定这个工厂能影响的区间：
[](https://imgse.com/i/pEFVDwn)
把这个区间全部变为这条直线就可以了。
由于整个函数是由很多直线（射线）构成的，使用单调栈维护就行，每次从栈底向顶找 $F(t)\ge c_{i}$，再把栈顶不优的全部弹掉，由于 $c_{i}\uparrow $，所以栈底指针也是单调增的（注意边界情况，实际写的时候最好找到了之后 `bottom--`）。
复杂度线性对数，瓶颈在于排序，实测跑得比二分快 $500ms$。
最后扫一遍函数找到第一个 $F(t)\ge S$ 的位置就好了。
**P.S.** 实际上本题对于下凸性质并没有利用，而是利用了单调性。
[Code](https://codeforces.com/contest/377/submission/301075114)。