1-独木桥（C）-526互联

少推一个性质……

题目描述

Alice和Bob是好朋友，有一天他们带了 $n$ 个孩子过独木桥。

为了方便，我们将问题抽象如下：

将独木桥看成一个长度无限长的实数轴，将每个孩子看作数轴上的一个实数点。数轴从左到右坐标不断增大。

孩子的位置用相对于数轴原点的点的坐标来表示。初始时 $n$ 个点在 $n$ 个互不相同的整点上。

每个点有一个初始朝向（从左向右或从右向左）。任何时刻所有的点都会以每秒 $1$ 单位长度的速度匀速向所朝的方向移动。当某一时刻两个点同时移动到了同一个位置上，它们会立即改变自己的朝向（从左向右变成从右向左，反之亦然），然后继续移动。

有 $q$ 次询问，每次询问给定 $k_{i}$ 与 $t_{i}$ ，询问在 $t_{i}$ 秒后，孩子 $k_{i}$ 目前的位置。

Bob 无法同时关注这么多的孩子，请你帮帮他。

题解

可以推出两个性质

容易发现如果不管标号的话，相遇时被或不被撞回去都是一样的，也就是说对于全等的两个人，继续向前走和两个人调换方向再走对于坐标来说都是没有区别的。
添加标号由于相遇之后会被撞回去，所以相对位置不变。

排序然后然后二分第 rank_k 个人即可，具体实现可以看代码。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,cnt[2],d[N],p[2][N],ranki[N];
struct ipt
{
    int p,i,d;
}ip[N];
bool cmp(const ipt& a,const ipt& b)
{
    return a.p<b.p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>ip[i].p;
        ip[i].i=i;
    }
    for(int i=0;i<n;++i)    cin>>ip[i].d;
    sort(ip,ip+n,cmp);
    for(int i=0;i<n;++i)
    {
        ranki[ip[i].i]=i;
        p[ip[i].d][cnt[ip[i].d]++]=ip[i].p;
    }
    cin>>q;
    for(int i=0,k,t,l,r,mid,ans;i<q;i++)
    {
        cin>>k>>t;
        k=ranki[k];
        l=0;
        ans=-1;
        r=cnt[0]-1;
        while(l<=r)
        {
            mid=l+r>>1;
            if(upper_bound(p[1],p[1]+cnt[1],p[0][mid]-2*t)-p[1]+mid<=k)
            {
                ans=mid;
                l=mid+1;
            }
            else    r=mid-1;
        }
        if(ans!=-1&&upper_bound(p[1],p[1]+cnt[1],p[0][ans]-2*t)-p[1]+ans==k)    cout<<p[0][ans]-t<<'\n';
        else    cout<<p[1][k-ans-1]+t<<'\n';
    }
    return 0;
}