题意

思路

先特判掉在同一个区域内的人，他们不需要桥，下面不考虑他们

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
    
     #define N 100005using 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
     
       fro;priority_queue
      
       
        ,greater
        
          > bac;bool cmp(Node a,Node b) {return a.l+a.r
         
          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<
          
           <