A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4071 [APIO2015] 巴邻旁之桥 线段树|平衡树|树状数组
发表于: | 分类: Oi | 评论:0 | 阅读:171

这应该是我这几天收获最多的一道题了,APIO出的题还是非常之妙的

题目大意:一条河岸,然后有很多人,每个人有自己想去的位置,可能在同侧或河岸对侧,你可以修建1/2座桥,求最少走的距离

这题是带子任务的,先看$k=1$的情况
首先如果两个东西在同侧,那可以先把他加到答案里面,这么没啥可说的
然后看如果过桥怎么办,我们假设桥现在建在了 $p$ 处,然后每个起点和终点分别是 $x_i,y_i$,显然有
$$ans = \sum{|x_i-p|+|y_i-p|}$$
再思考一下,我们把这些点放在一条数轴上,会发现其实$x_i,y_i$之间其实没啥区别,然后就变成了一堆点在数轴上,在数轴上确定一个点使得这个点到其他所有点的距离之和最小
这个点显然是中位数
不懂得看一下图吧

我们把点分为两半,显然左边的和右边对称的点连成的线段,只有在中间一段区间选点的时候才能每个值算一次
然后这个结论就显然了
然后思考$k=2$的时候怎么搞
先确立一个思路,这玩意应该是枚举分界点然后用第一个求
那么现在的重点就是用什么分界能保证最优性
再来看张图片吧
上下两个点分别是起点和终点,显然红色是目前的最优解
我们把红色向右平移,到了粉色和蓝色……好像没什么太大的变化,再平移到紫色,发现数值变大,再平移的时候发现越来越大
这里只花了一种情况,其余情况类似
考虑一种最特殊的情况,上下的位置相同,这个时候容易发现这样一个结论,桥距离$\frac{x_i+y_i}{2}$越近,这个答案就越小

所以我们可以按照$x_i+y_i$排序,然后枚举分界点,分别用$k=1$算两侧

现在考虑实现,我们需要一个东西快速插入删除求中位数
宋爷:我会平衡树 【笑
本人:我会线段树【笑

平衡树确实是随便维护了
考虑线段树的维护
可以记录一下他们坐标的前缀和$sum$,用线段树维护这个东西,再维护一下一个点i前面有几个数k
这样算前面所有点到他的距离就变成了 $sum-(k-1)*dis_i$,后面是同理的,这个东西在以前Usaco题里面用过的
然后正反求两遍就行了,省去了删除和两个线段树的问题

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
typedef long long LL;
const int N = 100000 +5 ;
const int M = N << 2;
using namespace std;
 
LL tr[M];
int cnt[M],T[N],tt;
 
LL F[N];
 
#define find(x) ( lower_bound(T+1,T+tt+1,x) - T )
 
void change(int k,int l,int r,int pos,int y)
{
    if(l == r) {tr[k] += y;cnt[k] ++; return;}
    int mid = (l+r) >> 1;
    if(pos <= mid) change(k<<1,l,mid,pos,y);
    else change(k<<1|1,mid+1,r,pos,y);
    tr[k] = tr[k<<1] + tr[k<<1|1], cnt[k] = cnt[k<<1] + cnt[k<<1|1];
}
 
LL ask(int rank)
{
    int k = 1, l = 1, r = tt, mid;
    LL tmp = 0;
    while(l<r)
    {
        mid = (l+r) >> 1;
        if(cnt[k<<1] < rank)
        {
            tmp += tr[k<<1];
            rank -= cnt[k<<1];
            l = mid + 1; k = k << 1|1;
        }
        else
            r = mid , k <<= 1;
    }
     
    return tr[1] - 2ll * tmp - 2ll * T[l] * rank;
}
 
struct data
{
    int L, R;
    bool operator < (const data &z)const
    {
        return L + R < z.L + z.R;
    }
}a[N];
 
inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
int main()
{
    int k = read(), n = read(),tmp1,tmp2;
    LL dis = 0;
    int tmpcnt = 0;
    char str1[5],str2[5];
    for(int i=1;i<=n;++i)
    {
        scanf("%s",str1);
        tmp1 = read();
        scanf("%s",str2);
        tmp2 = read();
        if(str1[0] == str2[0]) dis += abs(tmp2 - tmp1);
        else
        {
            T[++tt] = tmp1; T[++tt] = tmp2;
            if(tmp1 > tmp2) swap(tmp1,tmp2);dis++;
            a[++tmpcnt].L = tmp1; a[tmpcnt].R = tmp2;
        }
    }
    //cout << dis << endl;
    n = tmpcnt;
    sort(T+1,T+tt+1);
    int num = 0;
    T[0] = -1;
    for(int i=1;i<=tt;++i)
        if(T[i] != T[i-1])
            T[++num] = T[i];
    tt = num;
    sort(a+1,a+n+1);
     
    for(int i=1;i<=n;++i)
    {
        change(1,1,tt,find(a[i].L),a[i].L);
        change(1,1,tt,find(a[i].R),a[i].R);
        F[i] = ask(i);
    }
     
    if(k == 1)  
    {
        cout << F[n] + dis << endl;
        return 0;
    }
    memset(tr,0,sizeof tr);
    memset(cnt,0,sizeof cnt);
    LL ans = F[n] , tmp;
    for(int i=n;i;--i)
    {
        change(1,1,tt,find(a[i].L),a[i].L);
        change(1,1,tt,find(a[i].R),a[i].R);
        tmp = ask(n-i+1);
        ans = min(ans,tmp+F[i-1]);
    }
    cout << ans + dis << endl;
}

到这里还没结束
A了之后我一搜题解涨姿势了,这玩意可以直接树状数组维护
维护方法和倍增类似,每次直接在前面试着填上一个1,并加上该区间的值,如果区间值$>k$,就舍弃这个1,否则加上1,继续
最后位置+1就是答案。时间复杂度确实是一个非常小的$log$
非常巧妙

//C是树状数组
int find(int k,int *C)
{
    int ret=0,cnt=0;
    for(int i=17;i>=0;i--)
    {
        ret+=(1<<i);
        if(ret>len||cnt+C[ret]>=k) 
            ret-=(1<<i);
        else
            cnt+=C[ret];
    }
    return ret+1;
}


Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP