🎈 原创

洛谷 P1367 蚂蚁

题目描述

有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在 t 秒后的位置和朝向。

输入格式

第一行，两个空格隔开的整数 n，t（代表蚂蚁数 n 和时间 t）

第 2~n+1 行每行两个整数，第 i+1 行代表第 i 只蚂蚁的初始位置 ai（ai 的绝对值在 1000000 以内）及初始朝向 bi（bi=1 时蚂蚁朝右，bi=-1 时蚂蚁朝左）

输出格式

n 行，每行两个整数，第 i 行代表 t 秒后第 i 只蚂蚁的位置及朝向（-1 表示朝左，1 表示朝右，0 表示正在转向中）

输入输出样例

输入 #1复制

4 1
1 1
5 1
3 -1
10 1

输出 #1复制

2 0
6 1
2 0
11 1

说明/提示

【数据范围】

对于 40%的数据，n<=100

对于 80%的数据，n<=10000,t<=1000

对于 100%的数据，n<=100000,t<=100000

---

学习的是这篇题解https://blog.csdn.net/long_long_int/article/details/88351700

对于两只蚂蚁相遇，可以不考虑相遇后回头，而是让他们继续前进。经过观察可以发现，两只蚂蚁再相遇后会回头，因此蚂蚁的相对位置不会变动

相遇前：A---><---B相遇后：<---AB--->

因此可以将每只蚂蚁初始的顺序记录下来，最后移动后每个位置顺序上的蚂蚁还是对应之前顺序的那只。可以用 map 来实现记录。判断每只蚂蚁最后的朝向，也是只要对应顺序就可以了，对于正在转向的蚂蚁判断，可以再开一个 map，记录蚂蚁最后位置上的蚂蚁数，当数量超过 1 时，就认为这个位置上的蚂蚁相遇，正在转向。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

struct ANT
{
    int pos, dir, index;
}ants[100010];
int N, T;
bool cmpByPos(ANT a, ANT b)
{
    return a.pos < b.pos;
}
map<int, int> order;
map<int, int> cntOfPos;

int main(int argc, const char * argv[])
{
   cin >> N >> T;
   for(int i = 0; i < N; i++)
   {
       cin >> ants[i].pos >> ants[i].dir;
       ants[i].index = i;
   }
   sort(ants, ants + N, cmpByPos);
   for(int i = 0; i < N; i++)
       order[ants[i].index] = i;
   for(int i = 0; i < N; i++)
   {
       if(ants[i].dir == 1)
           ants[i].pos += T;
       else
           ants[i].pos -= T;
       cntOfPos[ants[i].pos]++;
   }
   sort(ants, ants + N, cmpByPos);
   for(int i = 0; i < N; i++)
   {
       cout << ants[order[i]].pos << " ";
       if(cntOfPos[ants[order[i]].pos] != 1)
           cout << 0;
       else
           cout << ants[order[i]].dir;
       cout << endl;
   }

    return 0;
}

说点题外话，这道题我之前在《挑战程序设计竞赛》上看到过相似的，介绍了对这种情况的处理方法，就是忽略转向，但是在考场上还是没做出这道题，感觉自己真的太弱了，唉。