[APIO2015]八邻旁之桥
2021-02-16 20:16
阅读：627
题面在这里
sol
这是一个\(Splay\)的题解
首先,如果一个人的家和办公室在同一侧,我们可以直接预处理;
如果不在同一侧,也可以加上1(当然要过桥啦)
当k==1时
我们设桥的位置为\(pos\),每个人的家的位置为\(x[i]\),办公室的位置为\(y[i]\),
则总代价为\(\sum_{i=1}^n (abs(x_i-pos)+abs(y_i-pos))\)
从这里我们可以看到,其实家和办公室的区别不是很明显。
所以这个问题可以简化为:
在数轴上任取一点a,最小化 \(\sum abs(a-x_i)\)
那么我们将所有家和办公室按照坐标排序,桥的位置肯定就在中间两个端点的位置之间
至于怎么统计相信大家都会吧(就在下面)
把所有家和办公室的坐标丢进一棵Splay中,平分
统计出左边的sum和右边的sum,左边的sz和右边的sz
当k==2时
再将上面的式子细分一下,我们能发现:
对于每条路径\(x[i]->y[i]\),其实际长度和\(1/2(x[i]+y[i])\)距离桥的距离有关
于是我们可以考虑将所有路径按照\((x[i]+y[i])\)排序
考虑建立两颗Splay
首先把所有的节点全部插入一棵Splay中去
然后一对一对(注意此处)的从老Splay中丢到另一棵Splay中去,一边统计答案
复杂度是O(nlogn)
应该是做完了
什么!!!!你被卡常了!!!!
在下提交的时候,第二个点总是TLE...交了无数遍的95分
看着机房的其他dalao都是用线段树做的,并不是很甘心啊......
但是方法总比困难多(hhhh)
具体可以参考我的代码
(一遍过的dalao可以略过)
代码
#includeif(i&&v[i]==x)cnt[i]++;
else{
i=++tot;
if(ff)s[v[ff]if(x==inf||x==-inf){
sz[i]=sum[i]=cnt[i]=0;
}
}
splay(i,0);
}
inline int find(int x){
RG int i=root;
while(v[i]!=x&&s[v[i]return i;
}
inline void Next(int x,int &lst,int &nxt){
RG int i=find(x);splay(i,0);
if(v[i]>x)nxt=i;
else {
nxt=s[1][i];
while(s[0][nxt])nxt=s[0][nxt];
}
if(v[i]else{
lst=s[0][i];
while(s[1][lst])lst=s[1][lst];
}
}
inline void Delete(int x){
RG int i=find(x);
cnt[i]--;splay(i,0);
}
inline int kth(int k){
RG int i=root;
while(1){
if(sz[s[0][i]]>=k)i=s[0][i];
else if(sz[s[0][i]]+cnt[i]>=k)return i;
else k-=sz[s[0][i]]+cnt[i],i=s[1][i];
}
}
inline ll bridge(){//这里是统计答案(不开long long可是会炸飞的)
if(empty())return 0;
int i=kth(sz[root]/2);splay(i,0);
return 1ll*sz[s[0][i]]*v[i]-sum[s[0][i]]+sum[s[1][i]]-1ll*sz[s[1][i]]*v[i];
}
}A,B;
inline ll input(ll n){
RG char p[5],q[5];
RG ll ans=0;RG int s,T;
cntt=0;
A.insert(inf);A.insert(-inf);
B.insert(inf);B.insert(-inf);
for(RG int i=1;i"%s",p+1);s=read();
scanf("%s",q+1);T=read();
if(p[1]!=q[1]){
ans++;
t[++cntt].l=s;t[cntt].r=T;
}
else ans+=abs(s-T);
}
sort(t+1,t+cntt+1);
for(RG int i=1;i/*
最关键的地方就是这里
直接记录一个Ans数组表示前i条路径全部走到一座桥上的答案
之后就不用删除了,把路径倒着插入另外一棵线段树中统计即可
*/
}
return ans;
}
inline void work2(int k,int n){
RG ll ans=input(n);
RG ll minn=Ans[cntt];
if(A.empty()){
printf("%lld\n",ans);
return;
}
for(RG int i=cntt;i>=1;i--){
B.insert(t[i].l);B.insert(t[i].r);
minn=min(minn,Ans[i-1]+B.bridge());
//倒插统计部分
}
printf("%lld\n",minn+ans);
}
inline void work1(int k,int n){
printf("%lld\n",input(n)+A.bridge());
}
int main()
{
RG int k,n;
k=read();n=read();
if(k^1)work2(k,n);
else work1(k,n);
return 0;
} 评论
亲，登录后才可以留言！