BZOJ 3709
? 有n只怪物，你的初始生命值为z。
? 为了打败第i只怪物，你需要消耗cost[i]点生命值，但怪物死后
会使你恢复val[i]点生命值。
? 任何时候你的生命值都不能小于等于0。
? 问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉
? n≤100,000
一些怪物是赚血的，一些是亏血的。
肯定要先打完所有赚血的，再打亏血的。
打赚血的：
为了保证能够有血，先打cos小的最保险。
微扰法证明：如果先打大一些的，如果能打，那么打小一些的也能打，而且血更多了，一定还能打那一个大的。
所以，先打小的一定不劣。
打亏血的：
为了保证能够有血，先打val大的最保险。
微扰法证明：为什么会出现一个方案能打，而另一个方案就打着打着就挂了呢？
一定有：life-cos1+val1-cos2<0并且life-cos2+val2-cos1>0
（显然，如果life-cos1<0且life-cos2>0的比较是没有必要的。因为处于减血的阶段，cos1就无论如何打不了了）
（所以只能是打了前一个，然后后一个不能打了）
即：life-cos2+val2-cos1>life-cos1+val1-cos2
那么，就有：val2>val1
并且，打1再打2和打2再打1之后的血量一致，不影响后面的。（也是微扰法的适用条件之一）
所以，当一个怪物的val更大的时候，先打它一定不劣。
用堆维护即可。
AGC 018 C
? 有X+Y+Z个人，每个人有Ai个金币，Bi个银币，Ci个铜币。现在
选X个人提供金币，Y个人提供银币，Z个人提供铜币。
? 求最多提供多少币。
? X+Y+Z≤100,000
话说直接跑费用流应该能过吧（虽然太暴力）
考虑如果只有金币银币。
如果1提供金币，2提供银币比换过来更优的话，有：A1+B2>A2+B1
A,B即金币银币。
移项：A1-B1>A2-B2
所以，按照A1-B1排序，前X个提供金币，后Y个提供银币。
现在加入铜币。
之前的努力不能白费。
所以我们在按照Ai-Bi排好序的数组上进行。
留坑
BZOJ 3709&&AGC 018 C——多段排序的微扰法
原文：https://www.cnblogs.com/Miracevin/p/9795328.html