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排好序的数组上进行。
枚举一个分界点,i
[1,i]用A,C来填,[i+1,X+Y+Z]用C,B来填。
两半分别用刚才的类似的排序方法求出来答案。
可以用堆维护到logn
为什么是对的?
对于我们填好的一个方案:ACACC|BBBCBB
'|'代表分界点
1.由于按照Ai-Bi排好序,所以,A和B交换不优。
2.由于分界点内部是按照Ai-Ci,Bi-Ci排序的,所以内部的A,C和B,C交换已经考虑过。
3.如果A跨过分界点和一个C交换,ACCCC|BBBABB,那么由于按照Ai-Bi排好序,所以换成ACCCC|ABBBBB会更优。
这个情况会在枚举下一个分界点的时候考虑到。
4.B跨过分界点和C交换同理。
所以,对于这样的排序方法,再加上枚举,一定可以遍历所有的可能成为最优解的方案。
总结:
1.猜结论
2.列出比较的式子。
3.枚举一维也是降低复杂度和思维含量的重要方法。