BZOJ4071 & 洛谷3644 & UOJ112：[APIO2015]巴邻旁之桥——题解

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

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

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

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

参考：https://www.cnblogs.com/zhenghaotian/p/8304917.html

对于同岸和走桥的代价先预处理，下面不在阐述。

k=1时，相当于找到一个点，使得所有起点和终点到该点的距离和最小。则我们排序在中间两点中间建桥则一定最优。就不证明了。

k=2时不能按k=1做（因为起点和终点需要用的桥是一样的），但是选桥的代价为（A起点，B桥，C终点）A->B->C，显然选一个近的桥最优，用程序表达的话就是离AC中点最近的桥。

所以以此排序，枚举分界点，其左右都是k=1的情况，用线段树做即可。

（简单聊下心路历程：开始k=1秒后想k=2，没考虑起点终点桥一样以为三分可过，结果第二个样例就跪了，后来思考之后排序后三分是O(nlog^2n)结果洛谷评测机死活没卡过去TAT果然还是太菜了我）

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

inline char getc(){

    char ch=;

    while(ch!='A'&&ch!='B')ch=getchar();

    return ch;

}

struct node{

    int l,r;

}q[N];

int m,tot,b[N];

ll num[][N*],sum[][N*],L[],R[];

bool cmp(node a,node b){return a.l+a.r<b.l+b.r;}

void LSH(){

    sort(b+,b+m+);

    m=unique(b+,b+m+)-b-;

    for(int i=;i<=tot;i++){

    q[i].l=lower_bound(b+,b+m+,q[i].l)-b;

    q[i].r=lower_bound(b+,b+m+,q[i].r)-b;

    }

}

void insert(int a,int l,int r,int k,ll w,int p){

    num[p][a]+=w,sum[p][a]+=w*b[k];

    if(l==r)return;

    int mid=(l+r)>>;

    if(k<=mid)insert(a*,l,mid,k,w,p);

    else insert(a*+,mid+,r,k,w,p);

}

int find(int a,int l,int r,int k,int p){

    if(l==r){

    L[]+=sum[p][a],L[]+=num[p][a];

    return b[l];

    }

    int mid=(l+r)>>;

    if(num[p][a*]>=k){

    R[]+=sum[p][a*+],R[]+=num[p][a*+];

    return find(a*,l,mid,k,p);

    }else{

    L[]+=sum[p][a*],L[]+=num[p][a*];

    return find(a*+,mid+,r,k-num[p][a*],p);

    }

}

int main(){

    int k=read(),n=read();

    ll ans=;

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

        char ch1=getc();

        ll u=read();

        char ch2=getc();

        ll v=read();

        if(ch1==ch2){

        ans+=abs(u-v);

        continue;

        }

        ans++;

        b[++m]=u,b[++m]=v;

        if(k==){

        q[++tot]=(node){u,v};

        }

    }

    if(k==){

        sort(b+,b+m+);

        for(int i=,j=m;i<j;i++,j--)ans+=b[j]-b[i];

        printf("%lld\n",ans);

    }else{

    if(!tot){

        printf("%lld\n",ans);

        return ;

    }

        sort(q+,q+tot+,cmp);

    LSH();

    for(int i=;i<=tot;i++){

        insert(,,m,q[i].l,,);

        insert(,,m,q[i].r,,);

    }

    int x=find(,,m,tot,);

    ll tmp=x*L[]-L[]+R[]-x*R[];

    for(int i=;i<tot;i++){

        insert(,,m,q[i].l,,);

        insert(,,m,q[i].r,,);

        insert(,,m,q[i].l,-,);

        insert(,,m,q[i].r,-,);

        ll all=;

        L[]=L[]=R[]=R[]=;

        x=find(,,m,i,);

        all+=x*L[]-L[]+R[]-x*R[];

        L[]=L[]=R[]=R[]=;

        x=find(,,m,tot-i,);

        all+=x*L[]-L[]+R[]-x*R[];

        tmp=min(tmp,all);

    }

    printf("%lld\n",ans+tmp);

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

秒客网

BZOJ4071 & 洛谷3644 & UOJ112：[APIO2015]巴邻旁之桥——题解

相关文章