Description:

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 \(A\) 和区域 \(B\)。每一块区域沿着河岸都建了恰好 \(1000000001\) 栋的建筑，每条岸边的建筑都从 \(0\) 编号到 \(1000000000\)。相邻的每对建筑相隔 \(1\) 个单位距离，河的宽度也是 \(1\) 个单位长度。区域 \(A\) 中的 \(i\) 号建筑物恰好与区域 \(B\) 中的 \(i\) 号建筑物隔河相对。城市中有 \(N\) 个居民。第 \(i\) 个居民的房子在区域 \(P_i\) 的 \(S_i\) 号建筑上，同时他的办公室坐落在 \(Q_i\) 区域的 \(T_i\) 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 \(K\) 座横跨河流的大桥。由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。当政府建造最多 \(K\) 座桥之后，设 \(D_i\) 表示第 \(i\) 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 \(D_1 + D_2 + \cdots + D_N\) 最小。输入输出格式

输入格式：

输入的第一行包含两个正整数 \(K\) 和 \(N\)，分别表示桥的上限数量和居民的数量。

接下来 \(N\) 行，每一行包含四个参数：\(P_i, S_i, Q_i\) 和 \(T_i\)，表示第 \(i\) 个居民的房子在区域 \(P_i\) 的 \(S_i\) 号建筑上，且他的办公室位于 \(Q_i\) 区域的 \(T_i\) 号建筑上。

输出格式：输出仅为一行，包含一个整数，表示 \(D_1 + D_2 + \cdots + D_N\) 的最小值。

Hint:

\(n \le 10^5\)

\(s_i,T_i \le 10^9\)

Solution:

显然对于在一边的居民可以直接统计

如果在两边,则不管是\(A->B\) 还是\(B->A\) 都是一样的

考虑问题的本质

把每个位置抽象成点

当k=1时,桥建在pos处

\(Ans=min \sum |i-pos|\)

这不就取个中位数吗

当k=2时

考虑一左一右划分成两个子问题

但如何将这些居民划分到两座桥上呢?

对于一个居民

发现选择离 $\frac{s_i + t_i} {2} $ 更近的桥会更优

于是按 $\frac{s_i + t_i} {2} $ 排序

按顺序枚举左和右的分界,每次分别对求中位数,更新答案

由于要进行动态插入和删除,故使用权值线段树实现

需要离散化,代码还是很好懂的

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ls p<<1#define rs p<<1|1using namespace std;typedef long long ll;const ll mxn=1e6+5;ll n,k,tot,cnt,p[mxn],sz[mxn<<2][2];ll ans,sum[mxn<<2][2];struct T {    ll x,y;}q[mxn];ll cmp(T a,T b) {    return a.x+a.y
         
          y) x=y;}void solve1(){ char a[2],b[2]; ll x,y; for(ll i=1;i<=n;++i) { scanf("%s %lld %s %lld",a,&x,b,&y); if(a[0]==b[0]) ans+=abs(x-y); else ++ans,p[++tot]=x,p[++tot]=y; } sort(p+1,p+tot+1); ll tp=p[tot>>1]; for(ll i=1;i<(tot>>1);++i) ans+=tp-p[i]; for(ll i=(tot>>1)+1;i<=tot;++i) ans+=p[i]-tp; printf("%lld",ans);}void update(ll id,ll l,ll r,ll tp,ll pos,ll val,ll p){ sz[p][id]+=val; sum[p][id]+=val*tp; if(l==r) return ; ll mid=(l+r)>>1;; if(pos<=mid) update(id,l,mid,tp,pos,val,ls); else update(id,mid+1,r,tp,pos,val,rs);}ll find(ll id,ll l,ll r,ll rk,ll p){ if(l==r) return l; ll mid=(l+r)>>1; if(rk<=sz[ls][id]) return find(id,l,mid,rk,ls); else return find(id,mid+1,r,rk-sz[ls][id],rs);}ll size(ll id,ll l,ll r,ll ql,ll qr,ll p){ if(ql<=l&&r<=qr) return sz[p][id]; ll mid=(l+r)>>1,res=0; if(ql<=mid) res+=size(id,l,mid,ql,qr,ls); if(qr>mid) res+=size(id,mid+1,r,ql,qr,rs); return res;} ll query(ll id,ll l,ll r,ll ql,ll qr,ll p) { if(ql<=l&&r<=qr) return sum[p][id]; ll mid=(l+r)>>1; ll res=0; if(ql<=mid) res+=query(id,l,mid,ql,qr,ls); if(qr>mid) res+=query(id,mid+1,r,ql,qr,rs); return res;}void solve2(){ char a[2],b[2]; ll x,y; for(ll i=1;i<=n;++i) { scanf("%s %lld %s %lld",a,&x,b,&y); if(a[0]==b[0]) ans+=abs(x-y); else ++ans,p[++tot]=x,p[++tot]=y,q[++cnt]=(T){x,y}; } if(!cnt) {printf("%lld",ans); exit(0);} //特判 sort(p+1,p+tot+1); tot=unique(p+1,p+tot+1)-p-1; sort(q+1,q+cnt+1,cmp); for(ll i=1;i<=cnt;++i) { q[i].x=lower_bound(p+1,p+tot+1,q[i].x)-p; q[i].y=lower_bound(p+1,p+tot+1,q[i].y)-p; } for(ll i=1;i<=cnt;++i) update(1,1,tot,p[q[i].x],q[i].x,1,1),update(1,1,tot,p[q[i].y],q[i].y,1,1); ll res=1e18; for(ll i=1;i<=cnt;++i) { update(0,1,tot,p[q[i].x],q[i].x,1,1),update(0,1,tot,p[q[i].y],q[i].y,1,1); update(1,1,tot,p[q[i].x],q[i].x,-1,1),update(1,1,tot,p[q[i].y],q[i].y,-1,1); ll lmid=find(0,1,tot,i,1),rmid=find(1,1,tot,cnt-i,1); ll u=1ll*size(0,1,tot,1,lmid,1)*p[lmid]-query(0,1,tot,1,lmid,1)+ query(0,1,tot,lmid,tot,1)-size(0,1,tot,lmid,tot,1)*p[lmid]; ll v=1ll*size(1,1,tot,1,rmid,1)*p[rmid]-query(1,1,tot,1,rmid,1)+ query(1,1,tot,rmid,tot,1)-size(1,1,tot,rmid,tot,1)*p[rmid]; res=min(res,u+v); } printf("%lld",ans+res);}int main(){ scanf("%lld%lld",&k,&n); if(k==1) solve1(); else solve2(); return 0;}