美团笔试

我用的模拟。一个数组存每个机器人的位置，一个数组存这个机器人是左还是右还是已经爆了，一个数组维护最后结果。维护两个值，一个是所有向左走的机器人当前位置最大值，一个是所有向右走的机器人当前位置最小值，当左最大值小于右最小值时停止计时。每秒钟先让向左的机器人统一向左走完，再统一处理向右的机器人。相遇了就将左状态或者右状态改成已经爆炸的状态。

按位置的奇偶分两组，先按位置排序，之后用堆栈的思想，往右走的push，往左走的看看pop（）个往右走的爆炸

第三题直接o3暴力可以过

我用的栈

我的方法可能效率不高 输入记为a[n][2] 把第一列复制一份到b[n] 然后对a进行以行为单位，以第一列为基准的排序 排序后寻找满足如下条件的一对元素： ① 左边元素的方向为R ② 右边元素的方向为L ③ 两点距离能被2整除 ④ 满足①②③的距离最短的两点，计算时间 循环找 直到找不到为止 排序会把顺序搞乱 所以最后用b数组比对一下输出顺序就ok了

暴力100%：           int n;  cin >> n;  vector<int> l, r，dis， v(n, -1);  for (int i = 0; i < n; ++i)  {   int m; char ch;     cin >> m >> ch;   if (ch == 'L&(6336)#39;) l.push_back(m);   else r.push_back(m);   dis.push_back(m);  }  sort(l.begin(), l.end());  sort(r.begin(), r.end());  int index1 = -1, index2 = -1;   do {   int md = INT_MAX;   index1 = -1, index2 = -1;   for (int j = 0; j < l.size(); ++j)   {    for (int k = 0; k < r.size(); ++k)    {     int d = l[j] - r[k]     if (d > 0&&d%2==0)     {      if (d < md)      {       md = d;       index1 = j;       index2 = k;      }     }    }   }   if (index1 != -1 && index2 != -1)   {    int i1 = find(dis.begin(), dis.end(), l[index1]) - dis.begin();    int i2 = find(dis.begin(), dis.end(), r[index2]) - dis.begin();    v[i1] = (l[index1] - r[index2]) / 2;    v[i2] = (l[index1] - r[index2]) / 2;    l.erase(l.begin() + index1);    r.erase(r.begin() + index2);   }  } while (index1 != -1 && index2 != -1);    for (int i : v) cout << i << endl;

首先题目要求整点相遇，因此你可以发现，奇数位置上的机器人只能和奇数位置上的相遇并爆炸（你可以很容易举出例子：位置1向右和位置2向左不可能爆炸，因为他们之间距离是奇数，不能在整点相遇），之后考虑如何处理爆炸：容易发现，假设一个向左的机器人要爆炸，在它之前的那些机器人中，只有奇偶性相同且位于最后的机器人才应该和他爆炸，因此这是典型的后进先出，考虑使用栈来进行这一过程

小美打车两个单元最短路即可，一个以起点按人走，一个以终点按车走，然后枚举每个起点，人走的和等车时间取最大值加上车走的，注意特殊情况起点就是终点