🎈 原创

洛谷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;
}

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