[luoguP3644] [APIO2015]八邻旁之桥（权值线段树）

2021-02-19 23:18

阅读：419

传送门

首先如果起点终点都在同一侧可以直接处理，如果需要过桥答案再加1

对于k等于1的情况

桥的坐标为x的话，a和b为起点和终点坐标

$ans=\sum_{1}^{n} abs(a_{i}-x)+abs(b_{i}-x)$

起点和终点显然可以合并

那么 $ans=\sum_{1}^{n} abs(a_{i}-x)$

x为中位数就是最优解

对于k等于2的情况

首先有个结论：$(a_{i}+b_{i})/2$ 离哪座桥近，就选择哪座桥

可以把坐标按照上面的公式排序，然后枚举中间点，分成左右两部分

每一部分都有一座桥，那么就需要一个可以维护中位数，求和，删除/增加一个数的数据结构

平衡树或者线段树都可以

#include 
#include 
#include 
#include 
#define N 200100
#define LL long long
#define root 1, 1, cnt
#define ls now > 1;
		if(x > 1;
		if(num[now = x)
		{
			R[0] += sum[now > 1];
	for(i = 1; i

上一篇：C#基础小记(一)

下一篇：windows批量删除ip

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[luoguP3644] [APIO2015]八邻旁之桥（权值线段树）
文章链接：http://soscw.com/index.php/essay/57739.html

亲，登录后才可以留言！

[luoguP3644] [APIO2015]八邻旁之桥（权值线段树）

评论

热门文章

推荐文章

最新文章

置顶文章