洛谷 P3644 [APIO2015]八邻旁之桥（对顶堆维护中位数）

题面传送门

题意：

一条河将大地分为 \(A,B\) 两个部分。两部分均可视为一根数轴。

有 \(n\) 名工人，第 \(i\) 名的家在 \(x_i\) 区域的 \(a_i\) 位置，公司在 \(y_i\) 区域的 \(b_i\) 位置。

现在你可以建立 \(k\) 座桥，在 \(x\) 位置建立一座桥可以连接 \(A\) 区域的 \(x\) 位置和 \(B\) 区域的 \(x\) 位置，桥长为 \(1\) 个单位长度。

设 \(d_i\) 为第 \(i\) 名工人从家到公司走过的最短距离，求 \(D=d_1+d_2+\dots+d_n\) 的最小值。

\(n \in [1,2\times 10^5],k\in\{1,2\},a_i,b_i \leq 10^9,x_i,y_i \in \{'A','B'\}\)。

一开始看错题了，以为 \(k\) 的数据范围也是 \(10^5\)。。。。。。然后就不愿意继续想下去了。

首先如果家和公司在河同一边那方案肯定是唯一的，直接加上 \(|a_i-b_i|\)。

接下来重点考虑家和公司不在河同一边的情况，假设这些工人 \(d_i\) 的和为 \(D'\)

先从 \(k=1\) 入手，假设我们在 \(p\) 位置建了座桥，那么所有家和公司不在河同一边都必须通过这一座桥，即 \(d_i=|a_i-p|+|b_i-p|+1\)。

\(D'=\sum |a_i-p|+|b_i-p|+1\)

最后那个 \(1\) 显然可以直接处理掉，剩余部分就是一个初一弱智数学问题，直接取中位数所有 \(a_i,b_i\) 就可以了。

接下来考虑 \(k=2\) 的情况。假设我们在 \(p,q\) 位置建了桥。

那么 \(d_i\) 就是从这两座桥上通过所需的距离的较小值，即 \(d_i=\min(|a_i-p|+|b_i-p|,|a_i-q|+|b_i-q|)+1\)。

在 \(k=1\) 的情况中，我们之所以能够把 \(a_i,b_i\) 揉在一起取中位数，是因为它们的贡献互不影响。

但在这种情况下就不能直接取中位数了，因为有个 \(\min\)。

不妨设 \(a_i \leq b_i\)，设 \(f(x)=|a_i-x|+|b_i-x|\)。简单画个图像，由三部分组成，左边是斜率为 \(-2\) 的射线，中间是一段水平线段，右边是斜率为 \(2\) 的射线。图像的对称轴为 \(x=\dfrac{a_i+b_i}{2}\)（梦回课内）

由于对称轴左右两边完全一样并且对称轴左边 \(y\) 随 \(x\) 的增大单调不降，故有：

若 \(|\dfrac{a_i+b_i}{2}-p|<|\dfrac{a_i+b_i}{2}-q|\)，那么 \(f(p)\leq f(q)\)。

有了这个结论，本题就简单多了。

把所有工人按 \(\dfrac{a_i+b_i}{2}\) 从小到大排序，那我们肯定是选择离 \(\dfrac{a_i+b_i}{2}\) 较近的那座桥。

不妨设 \(p<q\)，那么所有 \(\dfrac{a_i+b_i}{2}\leq\dfrac{p+q}{2}\) 的工人都会选择 \(p\) 那座桥，剩余的工人会选择 \(q\) 那座桥。

故选择 \(p\) 的工人是原序列的一个前缀，选择 \(q\) 的工人是原序列的一个后缀。

枚举断点 \(i\)，\([1,i]\) 的工人选择桥梁 \(p\)，\([i+1,n]\) 的工人选择桥梁 \(q\)。

断点两边是互相独立的。这时候我们又可以把绝对值拆开，于是我们又回到了第一问。

于是题目变为如何快速求出每个前缀的中位数，有 DS 味儿了，稍微一想就可以想到平衡树（

但稍微想一想就发现，其实根本不用平衡树。可以用两个堆来维护，建一个大根堆维护前一半的值，再建一个小根堆维护后一半的值。每次新插入一个值，就将它插入到对应的部分中，然后通过微调使两部分平衡。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fz(i,a,b) for(int i=a;i<=b;i++)

#define fd(i,a,b) for(int i=a;i>=b;i--)

#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a)

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

const int MAXN=1e5+5;

struct solver{

	multiset<int> st1,st2;

	ll sum1=0,sum2=0;

	void insert(int a){

		if(st1.empty()){

			st1.insert(a);sum1+=a;

		} else {

			int x=*st1.rbegin();

			if(a<=x) sum1+=a,st1.insert(a);

			else sum2+=a,st2.insert(a);

			int cnt=(st1.size()+st2.size()+1)/2;

			while(st1.size()>cnt){int v=*st1.rbegin();sum1-=v;sum2+=v;st1.erase(st1.find(v));st2.insert(v);}

			while(st1.size()<cnt){int v=*st2.begin();sum2-=v;sum1+=v;st2.erase(st2.find(v));st1.insert(v);}

		}

	}

	ll query(){

		if(st1.empty()) return 0;

		int cnt=(st1.size()+st2.size()+1)/2,x=*st1.rbegin();

		return 1ll*cnt*x-sum1+sum2-1ll*(st1.size()+st2.size()-cnt)*x;

	}

} x1,x2;

int n,k,m;

struct data{

	int a,b;

	friend bool operator <(data x,data y){

		return x.a+x.b<y.a+y.b;

	}

} f[MAXN];

ll sum=0;

ll pre[MAXN],suf[MAXN];

int main(){

	scanf("%d%d",&k,&n);

	for(int i=1;i<=n;i++){

		char x,y;int a,b;cin>>x>>a>>y>>b;

		if(x==y) sum+=abs(a-b);

		else f[++m].a=a,f[m].b=b,sum++;

	}

	if(k==1){

		for(int i=1;i<=m;i++) x1.insert(f[i].a),x1.insert(f[i].b);

		printf("%lld\n",x1.query()+sum);

	} else {

		sort(f+1,f+m+1);

		for(int i=1;i<=m;i++) x1.insert(f[i].a),x1.insert(f[i].b),pre[i]=x1.query();

		for(int i=m;i;i--) x2.insert(f[i].a),x2.insert(f[i].b),suf[i]=x2.query();

		ll mn=1e18;

		for(int i=1;i<=m+1;i++) mn=min(mn,pre[i-1]+suf[i]);

		printf("%lld\n",mn+sum);

	}

	return 0;

}

巴特西

洛谷 P3644 [APIO2015]八邻旁之桥（对顶堆维护中位数）

最新文章

热门文章