标签：

Description

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 A 和区域 B。

每一块区域沿着河岸都建了恰好 1000000001 栋的建筑，每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离，河的宽度也是 1 个单位长度。区域 A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。

城市中有 N 个居民。第 i 个居民的房子在区域 Pi 的 Si 号建筑上，同时他的办公室坐落在 Qi 区域的 Ti 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过 K 座横跨河流的大桥。

由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。当政府建造最多 K 座桥之后，设 Di 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 D1+D2+?+DN 最小。

 

Input

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

接下来 N 行，每一行包含四个参数：Pi,Si,Qi 和 Ti，表示第 i 个居民的房子在区域 Pi 的 Si 号建筑上，，且他的办公室位于 Qi 区域的 Ti 号建筑上。

 

Output

输出仅为一行，包含一个整数，表示 D1+D2+?+DN 的最小值。

 

Sample Input

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Sample Output

24

HINT

K=1或K=2

1≤N≤100000

 

题解

/*自己搞出来的一道题，真是好感动*/

为了方便，在同一侧的直接处理掉。

K=1时，显然就是取中位数。

K=2时，考虑每一对(S,T)，(绿蓝代表两座桥)，那么肯定是要选两条红线短的那一边。不过这样还不够好考虑，我们不如让着两条直线伸长相等的距离，延伸到中点。

于是对于每一对(S,T)，直接看Mid到两墙的距离就可以选择了。

进一步得出，如果我们把它们按中点排序，那么最后的局面肯定是，左部分都去桥1，右部分都去桥2，有一个分割点。

那么我们可以枚举分割点，分别计算两部分的最优桥，很神奇的把K=2分成了两个K=1，得到n^2的算法。

显然最优桥我们是可以动态维护的。

考虑点i(一对ST)，把它从右部分加入左部分。

那么它对于最优桥的影响是可以讨论的，过程很傻逼可以自己试一试。

我得到的结果是，考虑左右部分肯定都是偶数，那么另左部分中位数取(len/2)，右部分中位数取(len/2+1)，这么做比较方便。

然后加点到左部分的时候，因为我们已经按中点排序，所以只可能是一左一右或者两右(左右是相对当前最优桥而言的)。

那么如果是一左一右，最优桥不发生变化，对ans新的贡献也就是这个点的贡献。

如果是两右，会使最优桥右移一位，但对于之前已加入的点是没有影响的，ans的改变还是只有这个点。

于是用两个树状数组模拟两边，每次求最优桥(这个也用树状数组求第k小数)，然后维护ans也就是计算当前点的影响就行了。

复杂度O(nlogn)。说不清还是看代码吧。

主要考察数学建模、对数据结构的应用，感觉这题还是蛮好的。

代码

代码能力各种逗啊QwQ 调了好久 但调出来后真是好久没觉得这么爽了

#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=1e5+5; int abs(int x){return x>0?x:-x;} struct point{ int x,y,idx,idy,mid; bool operator <(const point&aa) const {return mid<aa.mid;} }a[maxn]; int b[maxn*2],l,len,k,n; ll ans; void prepare(){ for(int i=1;i<=l;i++) b[++len]=a[i].x,b[++len]=a[i].y; sort(b+1,b+len+1); for(int i=1;i<=l;i++){ if(a[i].x>a[i].y) swap(a[i].x,a[i].y); a[i].idx=lower_bound(b+1,b+len+1,a[i].x)-b; a[i].idy=lower_bound(b+1,b+len+1,a[i].y)-b; } } int S1[maxn*2],S2[maxn*2]; int lowbit(int o){return o&-o;} int add(int o,int k,int* C){ while(o<=len){ C[o]+=k; o+=lowbit(o); } } int find(int k,int *C){ int ret=0,cnt=0; for(int i=17;i>=0;i--){ ret+=(1<<i); if(ret>len||cnt+C[ret]>=k) ret-=(1<<i); else{ cnt+=C[ret]; } } return ret+1; } ll solve(){ ll ans1=0,ans2=0,ansx=0; prepare(); int A=0,B=b[len/2+1]; for(int i=1;i<=len;i++) ans2+=abs(B-b[i]); for(int i=1;i<=l;i++) add(a[i].idx,1,S2),add(a[i].idy,1,S2); ansx=ans2; for(int i=1;i<=l;i++){ int l1=i*2,l2=len-i*2; add(a[i].idx,1,S1);add(a[i].idy,1,S1); add(a[i].idx,-1,S2);add(a[i].idy,-1,S2); ans2-=abs(a[i].x-B)+abs(a[i].y-B); A=b[find(l1/2,S1)],B=b[find(l2/2+1,S2)]; ans1+=abs(a[i].x-A)+abs(a[i].y-A); if(ans1+ans2<ansx) ansx=ans1+ans2; } return ansx; } int main(){ char p,q; int u,v; scanf("%d%d",&k,&n); if(k==1){ ans=n; for(int i=1;i<=n;i++){ scanf("\n%c %d %c %d",&p,&u,&q,&v); if(p==q) ans+=abs(u-v),ans--; else b[++l]=u,b[++l]=v; } sort(b+1,b+l+1); int A=b[l/2]; for(int i=1;i<=l;i++) ans+=abs(A-b[i]); printf("%lld\n",ans); } else{ ans=n; for(int i=1;i<=n;i++){ l++; scanf("\n%c %d %c %d",&p,&a[l].x,&q,&a[l].y); if(p==q) ans+=abs(a[l].x-a[l].y)-1,l--; else a[l].mid=a[l].x+a[l].y; } sort(a+1,a+l+1); printf("%lld",ans+solve()); } return 0; }

【数学建模】【APIO2015】Palembang Bridges