[BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)

发布于 2018-02-17  89 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)

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

Http

BZOJ
Luogu

Tag

线段树,数论,离散化

解决思路

看到\(K\)的数据范围,要根据\(K==1\)和\(K==2\)分别讨论。
先把只在一边的单独算掉,排除在外。
首先\(K==1\)的情况,只有一座桥,那么就是所有人都要经过这个桥,假设这个桥的位置是pos,那么式子就是\(\sum (|A[i]-pos|+|B[i]-pos|)\),直接把\(A[i]\)和\(B[i]\)放在一起排序求出中位数即可。
然后是\(K==2\)的情况。有了前面的例子,我们可以知道,一个人一定是走离自己两边位置的中位数更近的那一座桥,那么可以把人按照中位数排序,枚举分割成两部分,两部分分别按照\(K==1\)的方式来算。
那么接下来的问题就是动态求中位数,这里用权值线段树的方式来求,具体来说就是找到中间的\(rank\),分割查看左边的大小与当前要查询的\(rank\)作比较,如果左边大于\(rank\)则走左边,否则走右边,类似于平衡树中求第\(K\)大。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=500100;
const int inf=2147483647;
const ll INF=1e18;

ll size,Num[maxN];//离散化并排序去重后的值域

class Segment//权值线段树
{
public:
    ll S[maxN*4];//记录区间数量和
    ll Sum[maxN*4];//记录区间权值和
    Segment()
        {
            mem(S,0);
        }
    void Modify(int now,int l,int r,int pos,ll opt)//单点修改
        {
            if (l==r){
                S[now]+=opt;Sum[now]+=opt*Num[l];return;
            }
            int mid=(l+r)>>1;
            if (pos<=mid) Modify(now*2,l,mid,pos,opt);
            if (pos>=mid+1) Modify(now*2+1,mid+1,r,pos,opt);
            S[now]=S[now*2]+S[now*2+1];Sum[now]=Sum[now*2]+Sum[now*2+1];
            return;
        }
    int GetMid()//得到中位数
        {
            return Querymid(1,1,size,S[1]/2);
        }
    int Querymid(int now,int l,int r,int q)//查询中位数
        {
            if (l==r) return l;
            int mid=(l+r)>>1;
            if (S[now*2]>=q) return Querymid(now*2,l,mid,q);
            else return Querymid(now*2+1,mid+1,r,q-S[now*2]);
        }
    ll Querysum(int now,int l,int r,int ql,int qr)//查询区间和
        {
            if ((l==ql)&&(r==qr)) return Sum[now];
            int mid=(l+r)>>1;
            if (qr<=mid) return Querysum(now*2,l,mid,ql,qr);
            if (ql>=mid+1) return Querysum(now*2+1,mid+1,r,ql,qr);
            return Querysum(now*2,l,mid,ql,mid)+Querysum(now*2+1,mid+1,r,mid+1,qr);
        }
    ll Querycnt(int now,int l,int r,int ql,int qr)//查询区间数字个数
        {
            if ((l==ql)&&(r==qr)) return S[now];
            int mid=(l+r)>>1;
            if (qr<=mid) return Querycnt(now*2,l,mid,ql,qr);
            if (ql>=mid+1) return Querycnt(now*2+1,mid+1,r,ql,qr);
            return Querycnt(now*2,l,mid,ql,mid)+Querycnt(now*2+1,mid+1,r,mid+1,qr);
        }
};

class RANGE
{
public:
    ll l,r;
};

bool operator < (RANGE A,RANGE B){//定义排序规则为按照中位数排序
    return A.l+A.r<B.l+B.r;
}

ll n,pl,K;
ll Ans=0;
ll L[maxN],R[maxN];
Segment S1,S2;
RANGE Range[maxN];

int Find(int key);

int main()
{
    ios::sync_with_stdio(false);//这一题输入如果用scanf好像有奇怪的错误,似乎是因为交替输入了字符和数字,所以这里用cin
    cin>>K>>n;
    for (int i=1;i<=n;i++)
    {
        char opt1,opt2;ll a,b;
        cin>>opt1>>a>>opt2>>b;
        if (opt1==opt2) Ans=Ans+abs(a-b);//在同一边的就直接加
        else
        {
            if (a>b) swap(a,b);
            pl++;L[pl]=a;R[pl]=b;
        }
    }
    if (K==1)//k=1直接排序处理
    {
        for (int i=pl+1;i<=pl+pl;i++) L[i]=R[i-pl];
        sort(&L[1],&L[pl+pl+1]);
        int pos=L[pl];
        for (int i=1;i<=pl+pl;i++) Ans=Ans+abs(L[i]-pos);
        printf("%lld\n",Ans+1ll*pl);
    }
    if (K==2)
    {
        if (pl==0){//特判剩余没有人的情况
            printf("%lld\n",Ans);
            return 0;
        }
        for (int i=1;i<=pl;i++){
            Num[i]=L[i];Num[i+pl]=R[i];
            Range[i].l=L[i];Range[i].r=R[i];
        }
        sort(&Num[1],&Num[pl+pl+1]);size=unique(&Num[1],&Num[pl+pl+1])-Num-1;sort(&Range[1],&Range[pl+1]);//离散化,同时将人排序

        for (int i=1;i<=pl;i++) S2.Modify(1,1,size,Find(Range[i].l),1),S2.Modify(1,1,size,Find(Range[i].r),1);//先把所有人都丢入第二棵线段树

        ll Ans2;int mid=S2.GetMid();//得到只建一座桥的答案
        Ans2=Num[mid]*S2.Querycnt(1,1,size,1,mid)-S2.Querysum(1,1,size,1,mid)+S2.Querysum(1,1,size,mid,size)-Num[mid]*S2.Querycnt(1,1,size,mid,size);

        for (int i=1;i<=pl;i++)
        {
            S1.Modify(1,1,size,Find(Range[i].l),1);S1.Modify(1,1,size,Find(Range[i].r),1);
            S2.Modify(1,1,size,Find(Range[i].l),-1);S2.Modify(1,1,size,Find(Range[i].r),-1);
            int md1=S1.GetMid(),md2=S2.GetMid();
            ll nowans
                =Num[md1]*S1.Querycnt(1,1,size,1,md1)-S1.Querysum(1,1,size,1,md1)+S1.Querysum(1,1,size,md1,size)-Num[md1]*S1.Querycnt(1,1,size,md1,size)
                +Num[md2]*S2.Querycnt(1,1,size,1,md2)-S2.Querysum(1,1,size,1,md2)+S2.Querysum(1,1,size,md2,size)-Num[md2]*S2.Querycnt(1,1,size,md2,size);
            Ans2=min(Ans2,nowans);
        }
        printf("%lld\n",Ans+Ans2+pl);
    }
    return 0;
}

int Find(int key)
{
    int l=1,r=size,ret=0;
    do
    {
        int mid=(l+r)>>1;
        if (Num[mid]<=key) ret=mid,l=mid+1;
        else r=mid-1;
    }
    while (l<=r);
    return ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)


HNCJ OIer