HDUOJ 6786 Intersection

题目链接

Problem Description

Mr. Left 来到了一个路口，这个路口只能右转，并且都是两车道。

现在在南北向车道上有 n 辆车，他们都在线 x 南边，这些车想要通过这个路口，到东边去，具体地说，他们要开到线 y 东边。

一辆车一个时刻可以从东南西北中选一个方向移动一个位置，或者呆在原地不动。
同一时刻同一位置不能有超过一辆车。车不能开到路外面。

在任意时刻，所有车都同时移动。两辆相邻的车不能都移动到对方的格子上。在此基础上，只要所有车移动后不存在两辆车处于同一位置，移动就合法。

问最少要多少时间，这些车才可以都开到东边？

Input

第一行一个整数 test (1≤test≤10)。

对于每组数据，第一行一个整数 n (1≤n≤100000)，表示车辆数目。

接下来 n 行，每行两个整数 x，y 表示车的位置，其中 x 表示车道 id（ x=1 表示右车道，x=2 表示左车道），y (1≤y≤100000) 表示车在路口前第几个位置。

数据保证没有两辆车初始在同一位置。

Output

对于每组数据，一行一个整数表示答案。

Sample Input

2
2
1 1
2 1
2
1 2
2 1

Sample Output

3
4

简单模拟，记录左车道和右车道每一辆车驶出的最短时间，如果时间有重则答案加一，遍历更新答案即可，AC代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    int n,m,x,y;
    scanf("%d",&t);
    while(t--){
        int ans=0;
        vector<int>car[3];
        map<int,int>m;
        scanf("%d",&n);
        while(n--){
            scanf("%d%d",&x,&y);
            car[x].push_back(y);
            int dis=y-1+(x==1?2:3);
            ans=max(ans,dis+m[dis]);
            m[dis]++;
        }
        printf("%d\n",ans);
    }
    return 0;
}