题意
有两排建筑,中间有一条河,给你每个人的起点和终点,现在你需要建k条桥,使得所有人起点到终点的距离最小,k=1或者2,n=100000
分析
先把同在一边的起点和终点给去掉
首先k=1的时候,很容易想到每个人都要过桥,然后每个人的距离就是
|s−p|+|t−p| | s − p | + | t − p |
p是桥的位置,s和t是起点和终点的位置,那么就是上式的贡献
再很容易发现这其实就是一个中位数模型
k=2的时候,我们考虑一个类似上面的做法
首先一个结论:每个点会选择的桥肯定是离 s+t2最近的 s + t 2 最 近 的
然后我们可以按照 s+t s + t 来排个序,然后枚举断点,断点左边的选左边的桥,断点右边的选右边的桥
然后就转化为一条桥的形式了
断点左边维护一颗权值线段树,断点右边也维护一颗,就可以支持找中位数啦
代码
#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf = e9;
const ll N = ;
const ll lg = ;
inline ll read()
{
ll p=; ll f=; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') f=-; ch=getchar();}
while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
return p*f;
}
ll lc[N*lg*2],rc[N*lg*2],c[N*lg*2],s[N*lg*2]; ll rt[],tot;
void link(ll &u,ll L,ll R,ll k,ll cc)
{
if(!u) u=++tot;
if(L==R){c[u] += cc; s[u] += L * cc; return ;}
ll mid=(L+R)>>;
if(k<=mid) link(lc[u],L,mid,k,cc);
else link(rc[u],mid+,R,k,cc);
c[u] = c[lc[u]] + c[rc[u]];
s[u] = s[lc[u]] + s[rc[u]];
}
ll qry(ll u,ll L,ll R,ll k)
{
if(L==R) return L;
ll mid=(L+R)>>;
if(c[lc[u]] >= k) return qry(lc[u],L,mid,k);
else return qry(rc[u],mid+,R,k-c[lc[u]]);
}
pair<ll,ll> qry2(ll u,ll L,ll R,ll l,ll r) // c s
{
if(l>r) return MP(,);
if(L == l && R == r) return MP(c[u],s[u]);
ll mid = (L+R)>>;
if(r<=mid) return qry2(lc[u],L,mid,l,r);
else if(l>mid) return qry2(rc[u],mid+,R,l,r);
else
{
pii ls = qry2(lc[u],L,mid,l,mid);
pii rs = qry2(rc[u],mid+,R,mid+,r);
return MP(ls.first + rs.first , ls.second + rs.second);
}
}
pair<ll,ll> q[N];
ll k,n; ll h[N],x[N],y[N];
int main()
{
k = read(); n = read(); ll ans = ,maxx;
ll nn = ; for(ll i=;i<=n;i++)
{
char ch1,ch2; ll xx,yy;
scanf("\n%c%lld\n%c%lld",&ch1,&xx,&ch2,&yy);
if(ch1 == ch2) ans += abs(xx-yy);
else ans++ , nn++, x[nn] = xx,y[nn] = yy , h[nn*2-] = xx,h[nn*2] = yy;
}n = nn;
if(k == )
{
sort(h+,h+*n+); ll mid = h[n];
for(ll i=;i<=*n;i++) ans = ans + abs(mid - h[i]);
printf("%lld\n",ans);
}
else
{
for(ll i=;i<=n;i++) q[i] = MP(x[i] + y[i] , i);
sort(q+,q+n+); rt[] = rt[] = tot = ;
for(ll i=;i<=n;i++){link(rt[],,inf,x[i],); link(rt[],,inf,y[i],);}
ll ls = ; ll rs = *n; ll mid = qry(rt[],,inf,rs>>); ll sum = ;
pii lmid = qry2(rt[],,inf,,mid); sum+=mid * lmid.first - lmid.second;
pii rmid = qry2(rt[],,inf,mid+,inf); sum+=rmid.second - mid * rmid.first;
maxx = sum; // printf("%lld\n",sum + ans);
for(ll i=;i<=n;i++)
{
ll pos = q[i].second;
link(rt[],,inf,x[pos],-); link(rt[],,inf,y[pos],-);
link(rt[],,inf,x[pos],); link(rt[],,inf,y[pos],);
ls+=; rs-=;
mid = qry(rt[],,inf,ls>>); sum = ;
lmid = qry2(rt[],,inf,,mid); sum+=mid * lmid.first - lmid.second;
rmid = qry2(rt[],,inf,mid+,inf); sum+=rmid.second - mid * rmid.first;
mid = qry(rt[],,inf,rs>>);
lmid = qry2(rt[],,inf,,mid); sum+=mid * lmid.first - lmid.second;
rmid = qry2(rt[],,inf,mid+,inf); sum+=rmid.second - mid * rmid.first;
maxx = min(maxx , sum); // printf("%lld\n",sum + ans);
}
printf("%lld\n",maxx + ans);
}
return ;
}