首页 > 其他分享 >【APIO2015】Palembang Bridges

【APIO2015】Palembang Bridges

时间:2023-03-07 16:24:02浏览次数:55  
标签:p2 Bridges p1 中位数 APIO2015 Palembang 排序 单调

容易想到先排除不用过桥的再把过桥的1加上,剩下只需要考虑河边走的距离。

首先考虑k=1的情况,容易发现相当于是一个直线上2n个点选一个点到所有点距离和最小,经典的结论选在中位数。
而k=2的时候,直觉告诉我们可以分组保证选择第一个桥的和第二个桥的排序后具有单调性,考虑一下这个方向。

一开始我想的是按照min排序,这样给定了p1,p2后,如果一个点不在p1,p2之间,那么他的最优方案已经固定了,这时候是满足单调性的。但是如果在p1,p2之间并且他们到达的点也是,那就没有单调性了。

我们于是考虑避免这一种情况的产生,发现只有上下两个点都在p1,p2内才会发生这个情况,这样绝对值就可以去掉,我们希望通过一种排序使得不会出现\(i<j\),满足\(calc(i,p2)<calc(i,p1)\)且\(calc(j,p1)<calc(j,p2)\)。

拆开一下,发现第一个式子等价于\(ai+bi>p1+p2\),第二个等价于\(aj+bj<p1+p2\),这时就显然易见了,我们只需要满足按照\(ai+bi\)排序就能避免这种情况。

现在我们就把问题分成了两个K=1的部分,只需要找到两侧的中位数即可。
中位数有2种方法(大概平衡树也可以用Kth来做但是我不太熟练):

  1. 线段树二分,很显然,码量略大。
  2. 用两个堆来实现,一个存前n个元素一个存后n个元素,我们发现是容易维护的。每次新加入之后只可能会出现一次小堆的max>大堆的min,这时候我们取出来再交换一下就行了。

Submissions:
线段树二分:https://uoj.ac/submission/88633
堆:https://uoj.ac/submission/610018

标签:p2,Bridges,p1,中位数,APIO2015,Palembang,排序,单调
From: https://www.cnblogs.com/IceYukino/p/17188471.html

相关文章

  • 【APIO2015】Bali Sculptures
    发现不是很好dp,考虑从大到小枚举位转而判断能不能让这一位为0。设计dp状态:\(dp[i][j]\)表示前i个分了j组是否能满足当前条件,显然有一个\(O(n^3logA)\)的简单dp。判断是否满......
  • 【APIO2015】Jakarta Skyscrapers
    很容易的想到根号分治,我们先考虑暴力做法。用dp[i][j]表示从开始状态到第i个点有一个跳跃能力为j的doge的最少跳跃次数,暴力也是O(n^2)的。我们考虑稍微优化优化。考虑根......
  • luogu P3644 [APIO2015] 八邻旁之桥
    Link题解首先忽略掉同侧的询问。对于\(K=1\),它其实就是问一个点到其它点的距离之和最小值,直接找到中位数然后计算即可。对于一条路线,我们可以发现,如果建的桥里这两个......
  • P3645 [APIO2015] 雅加达的摩天楼
    传送门思路这是一道纯纯暴力题,因为我们可以证明它的状态数不会超过\(n\sqrtn\)级别:若\(p\le\sqrtn\)时,显然状态数不会超过\(n\sqrtn\)若\(p>\sqrtn......