P3161 [CQOI2012] 模拟工厂
传送门：模拟工厂
问题描述：初始的生产力和商品分别为1和0。每一个时刻可以选择两个动作：生产力+1或者生产生产力数量的商品。现在有很多个订单，每个订单有三个部分：时间t，需要多少商品p，可以获得的价值v。现在需要决定各个时刻的动作选择，以及订单是否接取，以期获得最大收益。
本题在网上的题解有很多，但对于贪心策略的原理却鲜有说明。接下来我先介绍一下这道题的解题思路，然后简要说明贪心的原因：
订单总数最多只有15个，因此可以采用枚举的方式，遍历所有订单的选取情况，分别判断其可满足性，最终选取满足条件且使收益最大的订单选取情况。
枚举订单情况可以采用类似状态压缩的方法，也即遍历0~2^15-1，二进制数中的0和1表示订单选取情况。接下来主要讨论如何判断某一种订单选取情况是否满足条件。
对于某个订单选取情况，首先需要将选取的订单按照时间进行从小到大排序，然后从前往后处理。所有的题解都说明了下面这个推导式：假设当前生产力是M，当前订单距离下一个订单所需时间为T，要接取这个订单需要额外生产P个商品。假定在这个区间内我们选择长度为x的时间进行提高生产力（显然在小区间内，提高生产力的时间往前面放一定是更优的，因为这可以最大化这段区间内生产商品的数量），那么前x长度时间将生产力提升到(M+x)，而后(T-x)时间生产了(M+x)(T-x)数量的商品。可得如下不等式：
\[(M+x)(T-x)\ge P \]\[x^2+(M-T)x+P-M\cdot T\le0 \]假如这个不等式无解，说明不可能满足订单；如果有解，则在解区间内部选择最大的解x以尽可能提升生产力，x取值为：
\[\lfloor\frac{T-M+\sqrt{(M+T)^2-4P}}{2}\rfloor \]ps: 如果这个结果是一个负数，那么也说明无法满足该情况的解。有没有可能这个结果并不落在解区间内部？从方程来看有可能，因为解区间内部可能没有整数；但就本题而言，不存在该情况：因为两根之差为\(\sqrt{(M+T)^2-4P}\)，由于MTP都是整数，根号内部一定是整数，因此不会为(0,1)内的小数。
上面的描述中有一个疑点：为什么要尽可能提升生产力？这个问题之后会解释。先把算法整体描述清楚。
对于遍历到的某个具体的选取订单而言，根据其下一个订单利用上述公式解出x是否就行了？并不是，因为这个x有可能会导致后续的订单无法满足，也即将公式中的T和P更换成后续订单的数据可能导致x位于解区间右端点的右侧，也即该x对于后续订单来说偏大了。因此，需要对所有的后续订单都利用上式计算出一个端点，然后选取其中最小的作为当前订单后可以用于提升生产力的时间x。（T更新成到后续某个订单的时间，而P更新成到这个订单包括中间所有订单的商品总数）假如这个x解出来发现是负数（方程无解也返回一个负数），则说明订单无法满足。
最后来说明上述的贪心策略：为何要使得x在可取的范围内尽量大。首先，上述约束条件(x<=所有方程的右根)仅仅保证了x对于任何后续订单来说不会生产力过大导致商品不足，但并没有说x满足后续所有的方程，也即当前选取的x很有可能会处于后续方程的解区间左端点以左，也即x可能偏低，即对于后续的某一个订单而言，在当前提升了x的生产力后，可能出现生产力不足导致商品不足的情况（当前进一步提升生产力可以提高到该订单处的商品总数）。因此在合理范围内最大化生产力x，可以最大程度缓解后续可能出现的生产力不足带来的商品不足问题，并且也保证已经能够满足的订单不受影响。
以上为本人对本题贪心策略的思考，欢迎各位批评指正。
标签：洛谷,P3161,选取,说明,订单,生产力,区间,贪心,CQOI2012 From： https://www.cnblogs.com/z-xiang/p/18337084