适者

适者

我这题也是膜dalao的题解,这题用的是CDQ分治,也有用李超树的做法,其实两个复杂度是一样的了,就随便学一种就好。
首先考虑若一个炮塔都没有被秒杀,那么怎么安排攻击顺序最好
对于两个炮塔uv,若u在前那么v将多产生d[u] \times a[v]的伤害,vu前那么u将多产生d[v] \times a[u],显然我们要使伤害最小,即
当u在v前时,满足d[u] \times a[v]<d[v] \times a[u],整理得\frac{d[u]}{a[u]}<\frac{d[v]}{a[v]},等式两边都只与u或者v相关,满足偏序,排序一发即可。
再来考虑从中拿两个走,记拿x走总伤害减少c[x]
我们需要找到最大的i,j使得在第一次排序中ij前面,且c[i]+c[j]-d[i] \times a[j]最小
考虑对于每一个j,寻找能使上述表达式值最大的i
即使得c[i]-d[i] \times a[j],将它看成a[j]为自变量的一次函数,最后的取值显然是一个下突壳,单调队列维护即可,CDQ分治递归下去即可
可能说的有点抽象,给一下主程序的步骤:
1. 递归处理左右区间
2. 右区间按a[]排升序,即自变量从小到大
3. 左区间加入单调队列
4. 两个指针扫一下,把左区间的信息加到右区间上
5. 整个区间按d[]排序,即按斜率排升序(注意这里斜率取负数)

发表评论

电子邮件地址不会被公开。 必填项已用*标注