AGC023D Go Home | Arahc's Home

题面

简化题意

数轴上有 $n$ 栋楼，第 $i$ 栋楼位于 $x_i$ ，住了 $a_i$ 个人。现在这些人都在 $S$ ，要搭车回家。

乘车时，每一时刻，车上所有人投票决定向正方向走还是向负方向走，少数服从多数（同票则往负方向走）。每个人都按照自己尽早回家的策略投票。如果到了一栋房子门口，这里所有人都会下车。求最晚回家的人回家的时间。

$n\leq 10^5$ 。

题解

『自己尽早回家』真的等同于『每次投自己家的方向』吗？

对于上面的问题，考虑 $1,3,4$ 位置有房子，分别有 $3,4,2$ 个人，所有人最开始在 $2$ 。对于住在 $4$ 的人，如果他们投右边，则住在 $3$ 的人中途下车后，这些人就投不过住在 $1$ 的人了。因此会多绕路。

把这个实例形式化描述为：对于家住两端的人（设为 $x_l,x_r$ ），不妨设 $a_l<a_r$ ，此时住在 $x_l$ 的那些人会选择投右边，避免多绕路。

对于这种情况，不妨认为这些人直接“搬家”到 $x_r$ 住，最后强制对答案加上一个车走回来的路程 $x_r-x_l$ 即可。题目转化成了原问题的子问题。可以递归求解。递归边界为初始位置不在当前考虑的区间内，此时所有人都会投同一个方向。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,S,x[max_n],a[max_n];

inline int sol(int l,int r,int dir){
    if(S<x[l]) return x[r]-S;
    if(S>x[r]) return S-x[l];
    if(a[l]>=a[r]){
        a[l]+=a[r];
        return sol(l,r-1,1)+(dir==1?0:(x[r]-x[l]));
    }
    a[r]+=a[l];
    return sol(l+1,r,-1)+(dir==-1?0:(x[r]-x[l]));
}

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
    n=read(),S=read();
    for(register int i=1;i<=n;++i)
        x[i]=read(),a[i]=read();
    write(sol(1,n,a[1]>=a[n]?-1:1));
    return 0;
}