【BZOJ4071】【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 最小。 所有数据都保证: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大就走哪个,最后的叶节点就是中位数。。。
代码:
三分:(请木公爷来卡常啊啊啊)
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<queue> 7 #define inf 10000000000000000 8 #define eps 1e-9 9 using namespace std; 10 typedef long long ll; 11 struct pp{ 12 ll s1,s2,t1,t2; 13 }p[100001]; 14 ll n,K,ans=inf,l,r,maxn=0; 15 char sd1[2],sd2[2]; 16 ll gaogao(ll k,ll kk){ 17 ll ret=0; 18 for(ll i=1;i<=n;i++){ 19 if(p[i].s1==p[i].s2)ret+=abs(p[i].t1-p[i].t2); 20 else ret+=min(abs(p[i].t1-k)+abs(p[i].t2-k)+1,abs(p[i].t1-kk)+abs(p[i].t2-kk)+1); 21 } 22 return ret; 23 } 24 ll gao(ll k){ 25 if(K==1){ 26 ll ret=0; 27 for(ll i=1;i<=n;i++){ 28 if(p[i].s1==p[i].s2)ret+=abs(p[i].t1-p[i].t2); 29 else ret+=abs(p[i].t1-k)+abs(p[i].t2-k)+1; 30 } 31 return ret; 32 } 33 ll ret=inf,l=0,r=maxn; 34 while(l+3<=r){ 35 ll mid=l+(r-l)/3,mmid=r-(r-l)/3; 36 if(gaogao(k,mid)<=gaogao(k,mmid))r=mmid; 37 else l=mid; 38 } 39 for(ll i=l;i<=r;i++){ 40 ret=min(ret,gaogao(k,i)); 41 } 42 return ret; 43 } 44 int main(){ 45 scanf("%lld%lld",&K,&n); 46 for(ll i=1;i<=n;i++){ 47 scanf("%s%lld%s%lld",sd1,&p[i].t1,sd2,&p[i].t2); 48 p[i].s1=sd1[0]-'A'; 49 p[i].s2=sd2[0]-'A'; 50 maxn=max(maxn,max(p[i].t1,p[i].t2)); 51 } 52 l=0,r=maxn; 53 while(l+3<=r){ 54 ll mid=l+(r-l)/3,mmid=r-(r-l)/3; 55 if(gao(mid)<=gao(mmid))r=mmid; 56 else l=mid; 57 } 58 for(ll i=l;i<=r;i++){ 59 ans=min(ans,gao(i)); 60 } 61 printf("%lld",ans); 62 return 0; 63 }
权值线段树:
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #include<queue> 7 #define inf 1000000000000000 8 #define eps 1e-9 9 using namespace std; 10 typedef long long ll; 11 struct pp{ 12 ll t1,t2; 13 friend bool operator <(pp a,pp b){ 14 return a.t1+a.t2<b.t1+b.t2; 15 } 16 }p[200001]; 17 struct node{ 18 ll v,siz; 19 }t[1000001][2]; 20 ll n,k,t1,t2,x1,x2,x3,x4,m1,m2,nw1=0,nw2=0,els=0,sum=0,cnt=0,ans=inf,num[200001]; 21 char s1[2],s2[2]; 22 void updata(ll l,ll r,ll u,ll p,ll x,ll ch){ 23 t[u][ch].siz+=x; 24 t[u][ch].v+=x*num[p]; 25 if(l==r)return; 26 ll mid=(l+r)/2; 27 if(p<=mid)updata(l,mid,u*2,p,x,ch); 28 else updata(mid+1,r,u*2+1,p,x,ch); 29 } 30 ll get(ll l,ll r,ll u,ll x,ll ch){ 31 if(l==r)return l; 32 ll mid=(l+r)/2; 33 if(x<=t[u*2][ch].siz)return get(l,mid,u*2,x,ch); 34 else return get(mid+1,r,u*2+1,x-t[u*2][ch].siz,ch); 35 } 36 ll query(ll l,ll r,ll u,ll L,ll R,ll ch,ll xx){ 37 if(L<=l&&r<=R){ 38 return xx?t[u][ch].v:t[u][ch].siz; 39 } 40 ll mid=(l+r)/2,ret=0; 41 if(L<=mid)ret+=query(l,mid,u*2,L,R,ch,xx); 42 if(mid<R)ret+=query(mid+1,r,u*2+1,L,R,ch,xx); 43 return ret; 44 } 45 int main(){ 46 scanf("%lld%lld",&k,&n); 47 if(k==1){ 48 for(ll i=1;i<=n;i++){ 49 scanf("%s%lld%s%lld",s1,&t1,s2,&t2); 50 if(s1[0]==s2[0])els+=abs(t1-t2); 51 else{ 52 num[++cnt]=t1; 53 num[++cnt]=t2; 54 } 55 } 56 ans=els+cnt/2; 57 sort(num+1,num+cnt+1); 58 for(ll i=1;i<=cnt;i++){ 59 ans+=abs(num[i]-num[cnt/2]); 60 } 61 printf("%lld",ans); 62 }else{ 63 for(ll i=1;i<=n;i++){ 64 scanf("%s%lld%s%lld",s1,&t1,s2,&t2); 65 if(s1[0]==s2[0])els+=abs(t1-t2); 66 else{ 67 num[++cnt]=t1; 68 num[++cnt]=t2; 69 p[++sum].t1=t1; 70 p[sum].t2=t2; 71 } 72 } 73 if(!sum)return printf("%lld\n",els),0; 74 els+=sum; 75 sort(num+1,num+cnt+1); 76 cnt=unique(num+1,num+cnt+1)-num-1; 77 sort(p+1,p+sum+1); 78 for(ll i=1;i<=sum;i++){ 79 nw1+=p[i].t1+p[i].t2; 80 p[i].t1=lower_bound(num+1,num+cnt+1,p[i].t1)-num; 81 p[i].t2=lower_bound(num+1,num+cnt+1,p[i].t2)-num; 82 updata(1,cnt,1,p[i].t1,1,1); 83 updata(1,cnt,1,p[i].t2,1,1); 84 } 85 for(ll i=1;i<=sum;i++){ 86 nw2+=num[p[i].t1]+num[p[i].t2]; 87 nw1-=num[p[i].t1]+num[p[i].t2]; 88 updata(1,cnt,1,p[i].t1,1,0); 89 updata(1,cnt,1,p[i].t1,-1,1); 90 updata(1,cnt,1,p[i].t2,1,0); 91 updata(1,cnt,1,p[i].t2,-1,1); 92 m1=get(1,cnt,1,i,0); 93 m2=get(1,cnt,1,sum-i,1); 94 x1=query(1,cnt,1,1,m1,0,1); 95 x2=query(1,cnt,1,1,m2,1,1); 96 x3=query(1,cnt,1,1,m1,0,0); 97 x4=query(1,cnt,1,1,m2,1,0); 98 ans=min(ans,x3*num[m1]-x1+(nw2-x1)-(i*2-x3)*num[m1]+x4*num[m2]-x2+(nw1-x2)-((sum-i)*2-x4)*num[m2]); 99 } 100 printf("%lld",ans+els); 101 } 102 return 0; 103 }
转载于:.html
更多推荐
【BZOJ4071】【APIO2015】巴邻旁之桥
发布评论