自动搬运

查看原文

来自洛谷，原作者为

	UIai None

搬运于2025-08-24 21:48:41，当前版本为作者最后更新于2016-10-23 21:16:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实我们只需要将1~n这些人分向西向东两组扫两遍就可以了。

以向西行的第i人为例，最终停下来的无非三种情况

1.时间到了不能再走了

2.和在自己西边的向东走的i-1相撞了

3.和在自己西边的向西走的i-1相撞了（i-1与i-2相撞）

所以对于向西行的人我们只需要自西向东计算并记录每个人的位置即可，向东同理，详情见代码。

#include<iostream>
#define maxn 100010
using namespace std;
int n,Q,q[maxn];
long long loc[maxn],p[maxn][2],t;//loc记录第i个人的位置 
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>t>>Q;
    for(int i=1;i<=n;i++)
        cin>>p[i][0]>>p[i][1];    
    for(int i=1;i<=Q;i++)
        cin>>q[i];
    for(int i=1;i<=n;i++)
        if(p[i][1]==2)
        {
            if(i==1)
                loc[i]=p[i][0]-t;
            else if(p[i-1][1]==2)
                loc[i]=max(loc[i-1],p[i][0]-t);
            else loc[i]=max(p[i][0]/2+p[i-1][0]/2,p[i][0]-t);
        }
    for(int i=n;i>=1;i--)
        if(p[i][1]==1)
        {
            if(i==n)
                loc[i]=p[i][0]+t;
            else if(p[i+1][1]==1)
                loc[i]=min(loc[i+1],p[i][0]+t);
            else loc[i]=min(p[i][0]/2+p[i+1][0]/2,p[i][0]+t);
        }
    for(int i=1;i<=Q;i++)
        cout<<loc[q[i]]<<endl;
    return 0;
}