题解 P1367 【蚂蚁】

· · 题解

写在开头

你做过飞机吗？想象你在高空中看两个蚂蚁迎面相遇（当然不要考虑你能不能看得见），你会发现一件奇异的事情发生了——它们从对方的身上穿过去了！当然，只是它们互相绕过去而你没看清而已。

为什么要说这个呢？

我们来打个比方，假设有A,B两只蚂蚁头对头相遇。

1.对于你来说，--->AB<---（A,B迎面相遇）后，A<----->B（A,B都调头跑）是不是就相当于B<----->A（A,B互相穿过）。因为对于你来说它们就是两只蚂蚁？

2.对于蚂蚁来说，只要碰面就互相调换方向，假设A,B两只蚂蚁一前一后，无论双方面对什么方向，是不是B都超不过A？

总结： 综上所述，只要知道每只蚂蚁刚开始的相对位置排名，再特判走过t秒后两只蚂蚁位置是否相等，就可以通过相对位置排名输出！

但是怎么实现呢？

答案：排序排序再排序

下面是AC代码及具体讲解

#include<bits/stdc++.h>//万能头文件，美丽又大方
using namespace std;
int n,t,w[100001][2];//分别表示蚂蚁数量，时间长度，以及t秒后按位置从大到小排名后的位置及方向
struct node{//结构体方便排序
    int w,f,h,d;
}ant[100001];//记录信息，分别为每只蚂蚁的位置，方向，输入序号以及位置永久排名（位置排名不变）
int cmp(node x,node y){//排序方式1：按照位置排序
    return x.w<y.w;
}
int cmp1(node x,node y){//排序方式2：按照输入序号排序
    return x.h<y.h;
}
int main(){
    scanf("%d%d",&n,&t);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&ant[i].w,&ant[i].f);
        ant[i].h=i;
    }//简单输入以及标号
    sort(ant+1,ant+1+n,cmp);//按照t秒前的位置排序
    for (int i=1;i<=n;i++){
        ant[i].d=i;//定位永久位置排名
        ant[i].w+=ant[i].f*t;//模拟每个蚂蚁t秒后的位置
    }
    sort(ant+1,ant+1+n,cmp);//按照t秒后的位置排序
    for (int i=2;i<=n;i++){//判断是否正在转弯（如相邻两蚂蚁坐标相等，即为正在转弯）
        if (ant[i].w==ant[i-1].w){
            ant[i].f=0;ant[i-1].f=0;//标记输出时的状态
        }
    }
    for (int i=1;i<=n;i++){//填充记录从小到大蚂蚁的位置及方向
        w[i][0]=ant[i].w;
        w[i][1]=ant[i].f;
    }
    sort(ant+1,ant+1+n,cmp1);//按照输入序号排序
    for (int i=1;i<=n;i++){//按照输入时的顺序依次按照各自的永久位置输出每一只蚂蚁的坐标及状态
        printf("%d %d\n",w[ant[i].d][0],w[ant[i].d][1]);
    }
    return 0;//好习惯，人人养成
}

如果还有什么不明白的，可以在留言区私聊我哦，当然，如果你看完后明白了，动动你美丽漂亮可爱大方的小手点个赞吧，谢谢大家QAQ