分析1

我们先考虑\(m=1\)的时候的做法

对于子任务1,首先把所有的坐标离散出来,最多有\(2n\)个

然后暴力枚举\(2n\)的坐标的位置造桥,再\(O(n)\)计算代价

时间复杂度\(O(2n^2)\),期望得分8

紧接着考虑优化,我们发现,不需要每次花费\(O(n)\)来计算代价

我们只需要把所有的区间离散到坐标上,然后顺着扫一遍,直接记录一下,每次就可以\(O(1)\)修改得到代价

时间复杂度\(O(2n)\),期望得分22


分析2

然后在思考\(m=2\)做法的时候,猛然醒悟…自己原来是个煞笔…

我们在回过头去看\(m=1\)的时候

我们发现,答案由两部分组成,当两个建筑位于同一侧的时候\(ans1=|S_i-T_i|\),显然\(ans1\)是固定的

而第二部分的答案\(ans2=\sum |P_i-x|+|T_i-x|+1\),\(x\)表示桥的位置,显然当\(x\)集合\({S_i,T_i}\)的中位数的时候\(ans2\)取得最小值

时间复杂度\(O(nlogn)\),期望得分22


分析3

考虑\(m=2\)的做法

对于子任务3,同上述一样离散以后,暴力枚举两座桥的位置,然后花费\(O(n)\)计算代价

时间复杂度\(O(4n^3)\),期望得分9

继续考虑,我们可以发现,当有两座桥的时候,所有的居民唯一需要做的就是,找一座代价小的桥

而对于每一个居民而言,代价\(ans=|P_i-x|+|T_i-x|\),\(x\)为桥的位置,即如下图

那么,增加相同的距离,也就是说,我们需要比较\(\frac {P_i+T_i}{2}\)距离哪个比较近即可

这样,我们如果把所有的居民按照\(\frac {P_i+T_i}{2}\)排序的话,我们可以把所有的居民分成连续的两段,前一段使用前一座桥,后一段时候后一座桥

那么,我们把\(m=2\)问题,规约成了两个\(m=1\)问题

枚举断点,暴力的做\(m=1\)问题即可

时间复杂度\(O(n^2logn)\),期望得分41分,合并第一部分,可以得到63分,是一个很可观的分数了


分析4

继续考虑\(m=2\)的满分做法

我们得想办法把找中位数和算\(\sum |P_i-x|+|T_i-x|+1\)加速

我们每次会加入两个数字,或者删除两个数字,需要动态的维护中位数和上面的绝对值之和

用线段树来维护,很容易维护出中位数

那么绝对值怎么处理?显然,把绝对值拆开,因为,维护中位数的时候,顺便记录下中位数之前的和,然后就可以做啦

时间复杂度\(O(nlogn)\),期望得分100


满分程序

我的线段树写的比较丑QAQ

 


发表评论

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