线段树
同侧的显然不用管他。
k=1。枚举啊三分啊什么的应该都能过。进一步地，桥的位置一定是中位数。
k=2。发现没有什么二分三分之类的性质。假设两座桥已经定下来，那么一个居民会选择离(S+P)/2近的桥来走。也就是按(S+P)/2排序后，居民会被分成左右两波走不同的桥。那就枚举分界点，对于走同一座桥的，类似k=1的找出中位数，用线段数维护中位数。
#include<cstdio> #include<algorithm> #define N 100005 using namespace std; namespace runzhe2000 { typedef long long ll; char p1[3], p2[3]; int k, n, happy, dcnt, arr[N<<1], arrcnt; ll base, ans = 1ll<<60; struct data { int a, b, c; bool operator < (const data &that) const {return c < that.c;} }d[N]; struct segment_tree { struct seg { int siz; ll sum; }t[N*10]; void build(int x, int l, int r) { t[x].siz = t[x].sum = 0; if(l == r) return; int mid = (l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } int query_kth(int x, int l, int r, int k) { if(l == r) return l; int mid = (l+r)>>1; if(t[x<<1].siz >= k) return query_kth(x<<1,l,mid,k); else return query_kth(x<<1|1,mid+1,r,k-t[x<<1].siz); } ll query_sum(int x, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return t[x].sum; int mid = (l+r)>>1; ll ret = 0; if(ql <= mid) ret += query_sum(x<<1,l,mid,ql,qr); if(mid < qr) ret += query_sum(x<<1|1,mid+1,r,ql,qr); return ret; } int query_siz(int x, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return t[x].siz; int mid = (l+r)>>1; int ret = 0; if(ql <= mid) ret += query_siz(x<<1,l,mid,ql,qr); if(mid < qr) ret += query_siz(x<<1|1,mid+1,r,ql,qr); return ret; } void modi(int x, int l, int r, int p, int v, int type) { t[x].siz += type; t[x].sum += v*type; if(l == r)return; int mid = (l+r)>>1; if(p <= mid) modi(x<<1,l,mid,p,v,type); else modi(x<<1|1,mid+1,r,p,v,type); } void ins(data &x, int type) { modi(1,1,arrcnt,lower_bound(arr+1,arr+1+arrcnt,x.a)-arr,x.a,type); modi(1,1,arrcnt,lower_bound(arr+1,arr+1+arrcnt,x.b)-arr,x.b,type); } }t1, t2; int abs(int x){return x<0?-x:x;} void main() { happy = scanf("%d%d",&k,&n); for(int i = 1, x1, x2; i <= n; i++) { happy = scanf("%s%d%s%d",p1,&x1,p2,&x2); if(p1[0] == p2[0]) {base += abs(x1 - x2);i--;n--;} else d[++dcnt] = (data){x1, x2, (x1+x2)>>1}, arr[++arrcnt] = x1, arr[++arrcnt] = x2; } if(!n){printf("%lld\n",base);return;} sort(d+1, d+1+dcnt); sort(arr+1, arr+1+arrcnt); arrcnt = unique(arr+1, arr+1+arrcnt) - arr - 1; t1.build(1,1,arrcnt); t2.build(1,1,arrcnt); for(int i = 1; i <= n; i++) t2.ins(d[i],1); if(k == 1) { int mid = t2.query_kth(1,1,arrcnt,n); int ls = (1<=mid-1)?t2.query_siz(1,1,arrcnt,1,mid-1):0, rs = (mid+1<=arrcnt)?t2.query_siz(1,1,arrcnt,mid+1,arrcnt):0; ll ld = (1<=mid-1)?t2.query_sum(1,1,arrcnt,1,mid-1):0, rd = (mid+1<=arrcnt)?t2.query_sum(1,1,arrcnt,mid+1,arrcnt):0; ans = (ll)ls * arr[mid] - ld + rd - (ll)rs * arr[mid]; } else { for(int i = 1; i <= n; i++) { t1.ins(d[i],1); t2.ins(d[i],-1); ll tmp = 0; int mid = t1.query_kth(1,1,arrcnt,i); int ls = (1<=mid-1)?t1.query_siz(1,1,arrcnt,1,mid-1):0, rs = (mid+1<=arrcnt)?t1.query_siz(1,1,arrcnt,mid+1,arrcnt):0; ll ld = (1<=mid-1)?t1.query_sum(1,1,arrcnt,1,mid-1):0, rd = (mid+1<=arrcnt)?t1.query_sum(1,1,arrcnt,mid+1,arrcnt):0; tmp += (ll)ls * arr[mid] - ld; tmp += rd - (ll)rs * arr[mid]; mid = t2.query_kth(1,1,arrcnt,n-i); ls = (1<=mid-1)?t2.query_siz(1,1,arrcnt,1,mid-1):0, rs = (mid+1<=arrcnt)?t2.query_siz(1,1,arrcnt,mid+1,arrcnt):0; ld = (1<=mid-1)?t2.query_sum(1,1,arrcnt,1,mid-1):0, rd = (mid+1<=arrcnt)?t2.query_sum(1,1,arrcnt,mid+1,arrcnt):0; tmp += (ll)ls * arr[mid] - ld; tmp += rd - (ll)rs * arr[mid]; ans = min(ans, tmp); } } printf("%lld\n",ans+n+base); } } int main() { runzhe2000::main(); }