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.枚举一维也是降低复杂度和思维含量的重要方法。

05-11 09:32