题解 P3407 【散步】

UIai · 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;
}