链接
先特判掉在同一个区域内的人，他们不需要桥，下面不考虑他们
k==1时，即只有一座桥，假设它的位置是k，那么对于每个人i，他的贡献是\(|k-ai|+|k-bi|\)，可以看出这两部分的结构是一样的，可以分开看。于是问题就变成了有2n个人，求一个位置k，使得\(\Sigma_{i=1}^{2n}|ai-k|\)最小，这显然是求它们的中位数，sort一遍即可
k==2时，对于一个人i，\((ai+bi)/2\)离哪个桥近就从哪个桥过，这样一定是最优的（显然），于是对\((ai+bi)\)排个序，左边一部分人一定从左边的桥过，右边的一部分人从右边的桥过，我们只需要知道这个分界点在哪里就行了。 于是从1~n枚举这个分界点，两边分别按照k==1的方法来做即可 但是问题是这样做是\(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; }转载于:https://www.cnblogs.com/Chtholly/p/11325128.html
