-
先说一个我想的错误的贪心：先用单调栈把原序列构造成单增序列，选出 \(\lfloor \frac{K}{c_i} \rfloor = \lfloor \frac{K}{c_1} \rfloor\) 的最大的 \(i\) ，然后把剩下的余数选一个最大的 \(c_j\)
-
这个贪心显然是错误的，因为
3 3 2 0比3 3 1 1要优 -
正确做法是从低位到高位，每次看能把几个 \(c_{i-1}\) 位的值转成 \(c_i\) 位的值，注意特判不能超过上一位选择的数的个数。
-
最终复杂度 \(O(n)\)
CF1870D Prefix Purchase 题解
发布时间 2023-11-01 07:52:09作者: FOX_konata