注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4071][Apio2015]巴邻旁之桥  

2015-05-18 11:00:14|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4071: [Apio2015]巴邻旁之桥

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 43  Solved: 21
[Submit][Status][Discuss]

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

所有数据都保证:Pi 和 Qi 为字符 “A” 和 “B” 中的一个, 0≤Si,Ti≤1000000000,同一栋建筑内可能有超过 1 间房子或办公室(或二者的组合,即房子或办公室的数量同时大于等于 1)。

K<=2
1≤N≤100000

Solution

对于K=1的点,O(n)扫一遍就能出答案,然而考场上没有注意到实质是找中位数。
对于K=2的点,由于考场上写了个奇怪的式子,然后就不好往下推了。
实际上取每个线段的中点,如果靠近左边的桥,就往左边过桥,否则往右边过桥。
这样的话,先把线段按l+r排序,如果枚举在哪两座桥之间段开来的话,问题就转换成为K=1的情况了,线段树维护中位数。

Code

/**************************************************************
    Problem: 4071
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4476 ms
    Memory:13984 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
#define N 200010
int K,n,i,z[N],l,r,j,tot,m,cnt,t[1<<19],x,y;
ll ans,delta,f[N],sum[1<<19],tmp;
char s[6];
struct D{int l,r;}d[N],a[N];
bool operator<(const D&a,const D&b){return a.l+a.r<b.l+b.r;}
struct LS{int x,n;}ls[N];
bool operator<(const LS&a,const LS&b){return a.x<b.x;}
void ins(int o,int l,int r){
    if(l==r){
        t[o]++,sum[o]+=y;return;
    }
    int mid=l+r>>1;
    if(x<=mid)ins(o<<1,l,mid);
    else ins(o<<1|1,mid+1,r);
    t[o]=t[o<<1]+t[o<<1|1],sum[o]=sum[o<<1]+sum[o<<1|1];
}
ll query(int k){
    int o=1,l=1,r=cnt,mid;
    for(tmp=0;l<r;)
    if(mid=l+r>>1,t[o<<1]<k)tmp+=sum[o<<1],k-=t[o<<1],l=mid+1,o=o<<1|1;
    else r=mid,o<<=1;
    return sum[1]-tmp*2-2LL*z[l]*k;
}
int main(){
    for(scanf("%d%d",&K,&n),i=1;i<=n;i++){
        scanf("%s%d%s%d",s,&l,s+3,&r);
        if(l>r)j=l,l=r,r=j;
        if(s[0]==s[3])delta+=r-l;
        else delta++,d[++m]=(D){l,r};
    }
    n=m;std::sort(d+1,d+1+n);
    for(i=1;i<=n;i++)ls[++tot]=(LS){d[i].l,-i},ls[++tot]=(LS){d[i].r,i};
    std::sort(ls+1,ls+1+tot);ls[0].x=-1;
    for(i=1;i<=tot;i++){
        if(ls[i-1].x!=ls[i].x)z[++cnt]=ls[i].x;
        if(ls[i].n<0)a[-ls[i].n].l=cnt;else a[ls[i].n].r=cnt;
    }
    for(i=1;i<=n;i++){
        x=a[i].l,y=d[i].l,ins(1,1,cnt);
        x=a[i].r,y=d[i].r,ins(1,1,cnt);
        f[i]=query(i);
    }
    if(K==1)return printf("%lld\n",f[n]+delta),0;
    memset(sum,0,sizeof(sum));
    memset(t,0,sizeof(t));
    for(ans=f[n],i=n;i;i--){
        x=a[i].l,y=d[i].l,ins(1,1,cnt);
        x=a[i].r,y=d[i].r,ins(1,1,cnt);
        tmp=query(n-i+1);
        if(ans>tmp+f[i-1])ans=tmp+f[i-1];
    }
    printf("%lld\n",ans+delta);
}
  评论这张
 
阅读(272)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018