题意：

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 最小。

所有数据都保证：Pi 和 Qi 为字符 “A” 和 “B” 中的一个， 0≤Si,Ti≤1000000000 ，同一栋建筑内可能有超过 1 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 1）。
子任务 1 （8 分）K=1,1≤N≤1000
子任务 2 （14 分）K=1,1≤N≤100000
子任务 3 （9 分）K=2,1≤N≤100
子任务 4 （32 分）K=2,1≤N≤1000
子任务 5 （37 分）K=2,1≤N≤100000

Input

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

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

Output

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

题解：

首先，这题可以三分！可以三分！可以三分！

认（sui）真（bian）分（cai）析（xiang）一下可以发现，$K=1$时总花费时间随桥从左到右变化的函数是个单峰函数，$K=2$时是两个单峰函数通过某种变换之后叠加在一起，最后还是个单峰函数（然而我并不会证）

因此可以先三分第一个桥，再三分第二个桥，三分套三分的时间复杂度是$O(nlog^210^9)$的，手算大概有2.5亿，实测可以过掉前四个subtask，获得63分的好成绩（雾）

正解是权值线段树动态维护中位数。。。

$K=1$就不说了，大家都会。。。

$K=2$时有一个结论：每个人必定会走更接近$\frac{A_i+B_i}{2}$的那座桥，易得这样必定更优；

所以可以先按照$A_i+B_i$排序，左半边的人就会走左桥，右半边就走右桥；

然后就没了。。。左右各写一个数据结构，支持快速插入/删除，快速查询中位数和区间和，可以直接splay，也可以用权值线段树黑科技来做（新技能get√）

ps：所谓的黑科技就是，左右儿子哪个size大就走哪个，最后的叶节点就是中位数。。。

代码：

三分：（请木公爷来卡常啊啊啊）

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 10000000000000000

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 struct pp{

     ll s1,s2,t1,t2;

 }p[];

 ll n,K,ans=inf,l,r,maxn=;

 char sd1[],sd2[];

 ll gaogao(ll k,ll kk){

     ll ret=;

     for(ll i=;i<=n;i++){

         if(p[i].s1==p[i].s2)ret+=abs(p[i].t1-p[i].t2);

         else ret+=min(abs(p[i].t1-k)+abs(p[i].t2-k)+,abs(p[i].t1-kk)+abs(p[i].t2-kk)+);

     }

     return ret;

 }

 ll gao(ll k){

     if(K==){

         ll ret=;

         for(ll i=;i<=n;i++){

             if(p[i].s1==p[i].s2)ret+=abs(p[i].t1-p[i].t2);

             else ret+=abs(p[i].t1-k)+abs(p[i].t2-k)+;

         }

         return ret;

     }

     ll ret=inf,l=,r=maxn;

     while(l+<=r){

         ll mid=l+(r-l)/,mmid=r-(r-l)/;

         if(gaogao(k,mid)<=gaogao(k,mmid))r=mmid;

         else l=mid;

     }

     for(ll i=l;i<=r;i++){

         ret=min(ret,gaogao(k,i));

     }

     return ret;

 }

 int main(){

     scanf("%lld%lld",&K,&n);

     for(ll i=;i<=n;i++){

         scanf("%s%lld%s%lld",sd1,&p[i].t1,sd2,&p[i].t2);

         p[i].s1=sd1[]-'A';

         p[i].s2=sd2[]-'A';

         maxn=max(maxn,max(p[i].t1,p[i].t2));

     }

     l=,r=maxn;

     while(l+<=r){

         ll mid=l+(r-l)/,mmid=r-(r-l)/;

         if(gao(mid)<=gao(mmid))r=mmid;

         else l=mid;

     }

     for(ll i=l;i<=r;i++){

         ans=min(ans,gao(i));

     }

     printf("%lld",ans);

     return ;

 }

权值线段树：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 1000000000000000

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 struct pp{

     ll t1,t2;

     friend bool operator <(pp a,pp b){

         return a.t1+a.t2<b.t1+b.t2;

     }

 }p[];

 struct node{

     ll v,siz;

 }t[][];

 ll n,k,t1,t2,x1,x2,x3,x4,m1,m2,nw1=,nw2=,els=,sum=,cnt=,ans=inf,num[];

 char s1[],s2[];

 void updata(ll l,ll r,ll u,ll p,ll x,ll ch){

     t[u][ch].siz+=x;

     t[u][ch].v+=x*num[p];

     if(l==r)return;

     ll mid=(l+r)/;

     if(p<=mid)updata(l,mid,u*,p,x,ch);

     else updata(mid+,r,u*+,p,x,ch);

 }

 ll get(ll l,ll r,ll u,ll x,ll ch){

     if(l==r)return l;

     ll mid=(l+r)/;

     if(x<=t[u*][ch].siz)return get(l,mid,u*,x,ch);

     else return get(mid+,r,u*+,x-t[u*][ch].siz,ch);

 }

 ll query(ll l,ll r,ll u,ll L,ll R,ll ch,ll xx){

     if(L<=l&&r<=R){

         return xx?t[u][ch].v:t[u][ch].siz;

     }

     ll mid=(l+r)/,ret=;

     if(L<=mid)ret+=query(l,mid,u*,L,R,ch,xx);

     if(mid<R)ret+=query(mid+,r,u*+,L,R,ch,xx);

     return ret;

 }

 int main(){

     scanf("%lld%lld",&k,&n);

     if(k==){

         for(ll i=;i<=n;i++){

             scanf("%s%lld%s%lld",s1,&t1,s2,&t2);

             if(s1[]==s2[])els+=abs(t1-t2);

             else{

                 num[++cnt]=t1;

                 num[++cnt]=t2;

             }

         }

         ans=els+cnt/;

         sort(num+,num+cnt+);

         for(ll i=;i<=cnt;i++){

             ans+=abs(num[i]-num[cnt/]);

         }

         printf("%lld",ans);

     }else{

         for(ll i=;i<=n;i++){

             scanf("%s%lld%s%lld",s1,&t1,s2,&t2);

             if(s1[]==s2[])els+=abs(t1-t2);

             else{

                 num[++cnt]=t1;

                 num[++cnt]=t2;

                 p[++sum].t1=t1;

                 p[sum].t2=t2;

             }

         }

         if(!sum)return printf("%lld\n",els),;

         els+=sum;

         sort(num+,num+cnt+);

         cnt=unique(num+,num+cnt+)-num-;

         sort(p+,p+sum+);

         for(ll i=;i<=sum;i++){

             nw1+=p[i].t1+p[i].t2;

             p[i].t1=lower_bound(num+,num+cnt+,p[i].t1)-num;

             p[i].t2=lower_bound(num+,num+cnt+,p[i].t2)-num;

             updata(,cnt,,p[i].t1,,);

             updata(,cnt,,p[i].t2,,);

         }

         for(ll i=;i<=sum;i++){

             nw2+=num[p[i].t1]+num[p[i].t2];

             nw1-=num[p[i].t1]+num[p[i].t2];

             updata(,cnt,,p[i].t1,,);

             updata(,cnt,,p[i].t1,-,);

             updata(,cnt,,p[i].t2,,);

             updata(,cnt,,p[i].t2,-,);

             m1=get(,cnt,,i,);

             m2=get(,cnt,,sum-i,);

             x1=query(,cnt,,,m1,,);

             x2=query(,cnt,,,m2,,);

             x3=query(,cnt,,,m1,,);

             x4=query(,cnt,,,m2,,);

             ans=min(ans,x3*num[m1]-x1+(nw2-x1)-(i*-x3)*num[m1]+x4*num[m2]-x2+(nw1-x2)-((sum-i)*-x4)*num[m2]);

         }

         printf("%lld",ans+els);

     }

     return ;

 }

巴特西

【BZOJ4071】【APIO2015】巴邻旁之桥

题意：

Description

Input

Output

题解：

代码：

最新文章

热门文章