[CQOI2012]模拟工厂 题解(搜索+贪心)
标签：题解
阅读体验：链接题目地址：
这个题练一练综合思想还是不错的。。。（然而蒟蒻不会啊）做法
肯定是在能完成某些订单的情况下使自己生产力越高越好是吧（一个大致的贪心方向）
但是我们不知道自己到底应该怎么去决定提高生产力时间 那么换个角度，不从时间来看，从订单上来看贪心
我们假设一定要完成订单\(1～n\)
那么应该如何贪心选时间提升生产力呢，当然是在能满足所有订单的基础上尽量多地提高生产力 那么对于订单\(i\)和\(j\)，我们都会得到方程：(设\(pdc(produce)\)为完成订单\(i\)时的生产力，\(T\)为距离\(j\)订单的时间，\(x\)为用来提升生产力的时间，\(gv(give)\)是订单\(j\)需求量)\[(pdc+x)×(T-x)=gv\]对所有我们一定要完成的订单一个一个完成，每次完成一个订单时对它之后的每一个订单我们都解这么一个方程，得到尽可能的休息时间，那么这样子一定是对的吧然后可以想到
上面是\(1～n\)我们都想完成，现在不同了，我们可以放弃一些订单
再看数据范围：\(n<=15\)？，那不就暴力枚举状态选还是不选啊 然后对于上面那个方程，如果无解\(△ < 0\)肯定这种计划是不行的 然后直接用求根公式会得到：\[\frac{T-pdc+\sqrt{(pdc+T)^2-4×gv}}{2}\]算一下时间复杂度：\(O(2^n×n^2)\)很对呀，那就做完了给出代码
哼哼～压行是看代码人的噩梦，是写代码者的美梦（虽然笔者只稍稍压行了。。。）
#include#define il inline#define rg register#define ldb double#define lst long long#define rgt register int#define N 20#define M 100050using namespace std;const int Inf=1e9;il lst MAX(rg lst x,rg lst y){return x>y?x:y;}il lst MIN(rg lst x,rg lst y){return x