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

时间:2023-03-08 15:59:32

https://www.lydsy.com/JudgeOnline/problem.php?id=4071

https://www.luogu.org/problemnew/show/P3644

http://uoj.ac/problem/112

一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域 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/+

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