考虑K=1的情况，首先家和公司在同侧的直接统计到答案里，并删去。 然后剩下的都在两边，我们就是要最小化 ∑i|ai−x|+[bi−x| ∑ i | a i − x | + [ b i − x | 其实就是求所有坐标的中位数。 考虑K=2的情况，把所有的人按家和公司的中点从小到达排序，那么一定存在一个分割点，使得他左面的人都走左面的桥，他右面的人都走右面的桥。（因为一个人走离他中点最近的桥肯定不差） 这样我们枚举这个分割点即可，用线段树动态维护区间中位数即可。 复杂度 O(nlogn) O ( n l o g n )
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int n,aa[N<<1],m=0,nn=0,cnt=0; ll ans=0,sum=0; struct P{ int x,y; friend bool operator<(P a,P b){return a.x+a.y<b.x+b.y;} }a[N]; struct node{ ll sum;int x; }tr[2][N<<3]; inline void ins(int id,int p,int l,int r,int x,int val){ tr[id][p].sum+=aa[x]*val;tr[id][p].x+=val; if(l==r) return;int mid=l+r>>1; if(x<=mid) ins(id,p<<1,l,mid,x,val); else ins(id,p<<1|1,mid+1,r,x,val); } inline int ask(int id,int p,int l,int r,int x){ if(l==r){sum+=tr[id][p].sum;cnt+=tr[id][p].x;return aa[l];}int mid=l+r>>1; if(x<=tr[id][p<<1].x) return ask(id,p<<1,l,mid,x); sum+=tr[id][p<<1].sum;cnt+=tr[id][p<<1].x;return ask(id,p<<1|1,mid+1,r,x-tr[id][p<<1].x); } int main(){ // freopen("a.in","r",stdin); int op=read();n=read(); for(int i=1;i<=n;++i){ char c1[2],c2[2]; scanf("%s",c1);int x=read();scanf("%s",c2);int y=read();if(x>y) swap(x,y); if(c1[0]==c2[0]){ans+=y-x;continue;} a[++m].x=x;a[m].y=y;aa[++nn]=x;aa[++nn]=y; }sort(aa+1,aa+nn+1);ans+=m; if(op==1){ for(int i=1,j=nn;i<=j;++i,--j) ans+=aa[j]-aa[i]; printf("%lld\n",ans);return 0; }if(!m){printf("%lld\n",ans);return 0;} n=unique(aa+1,aa+nn+1)-aa-1;sort(a+1,a+m+1); for(int i=1;i<=m;++i){ a[i].x=lower_bound(aa+1,aa+n+1,a[i].x)-aa; a[i].y=lower_bound(aa+1,aa+n+1,a[i].y)-aa; ins(1,1,1,n,a[i].x,1);ins(1,1,1,n,a[i].y,1); }cnt=0;sum=0;ll x=ask(1,1,1,n,m); ll res=tr[1][1].sum-sum-sum+(cnt-(tr[1][1].x-cnt))*x; for(int i=1;i<=m;++i){ ins(1,1,1,n,a[i].x,-1);ins(1,1,1,n,a[i].y,-1); ins(0,1,1,n,a[i].x,1);ins(0,1,1,n,a[i].y,1); cnt=0;sum=0;ll x=ask(0,1,1,n,i); ll tmp=tr[0][1].sum-sum-sum+(cnt-(tr[0][1].x-cnt))*x; cnt=0;sum=0;x=ask(1,1,1,n,m-i); tmp+=tr[1][1].sum-sum-sum+(cnt-(tr[1][1].x-cnt))*x;res=min(res,tmp); }printf("%lld\n",ans+res); return 0; }