题意
思路
先特判掉在同一个区域内的人,他们不需要桥,下面不考虑他们
k==1时,即只有一座桥,假设它的位置是k,那么对于每个人i,他的贡献是(|k-ai|+|k-bi|),可以看出这两部分的结构是一样的,可以分开看。于是问题就变成了有2n个人,求一个位置k,使得(Sigma_{i=1}^{2n}|ai-k|)最小,这显然是求它们的中位数,sort一遍即可
k2时,对于一个人i,((ai+bi)/2)离哪个桥近就从哪个桥过,这样一定是最优的(显然),于是对((ai+bi))排个序,左边一部分人一定从左边的桥过,右边的一部分人从右边的桥过,我们只需要知道这个分界点在哪里就行了。
于是从1~n枚举这个分界点,两边分别按照k1的方法来做即可
但是问题是这样做是(n^2)的复杂度(枚举n*求值n),考虑优化一下求中位数的过程
动态维护中位数,用两个堆维护即可,咕咕模板
Code:
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
const ll INF = 10000000000000000;
int k,n,p;
ll ans,tpr,a[N<<1];
ll rsum,lsum,sum[N];
struct Node
{
ll l,r;
}nd[N];int cnt;
priority_queue<int> fro;
priority_queue<int,vector<int>,greater<int> > bac;
bool cmp(Node a,Node b) {return a.l+a.r<b.l+b.r;}
void insert(ll x)
{
if(fro.empty()) {fro.push(x);lsum+=x;}
else if(x>fro.top()) {bac.push(x);rsum+=x;}
else {fro.push(x);lsum+=x;}
while(abs((int)bac.size()-(int)fro.size())>1)
{
if(bac.size()>fro.size())
{
ll x=bac.top();
bac.pop();rsum-=x;
fro.push(x);lsum+=x;
}
else
{
ll x=fro.top();
fro.pop();lsum-=x;
bac.push(x);rsum+=x;
}
}
}
int main()
{
scanf("%d%d",&k,&n);
for(int i=1;i<=n;++i)
{
char c[2],d[2];int x,y;
scanf("%s%d%s%d",c,&x,d,&y);
if(c[0]==d[0]) {ans+=abs(y-x);continue;}
nd[++cnt]=(Node){min(x,y),max(x,y)};
a[++p]=x;
a[++p]=y;
}
sort(a+1,a+p+1);
for(int i=1;i<=p;++i) tpr+=abs(a[i]-a[cnt]);
if(k==2)
{
sort(nd+1,nd+cnt+1,cmp);
for(int i=1;i<=cnt;++i)
{
insert(nd[i].l);
insert(nd[i].r);
sum[i]=rsum-lsum;
}
while(!fro.empty()) fro.pop();
while(!bac.empty()) bac.pop();
rsum=lsum=0;
for(int i=cnt;i>=1;--i)
{
sum[i]+=rsum-lsum;
insert(nd[i].l);
insert(nd[i].r);
}
for(int i=1;i<=cnt;++i) tpr=min(tpr,sum[i]);
}
cout<<ans+tpr+cnt<<endl;
return 0;
}