【洛谷P1367】蚂蚁

蚂蚁

【题目描述】

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

 

思路：

1.对于每只蚂蚁，它的坐标在所有蚂蚁中的次序无论怎样移动都不会改变。（因为当两只蚂蚁相遇时，它们会掉头）

2.对于两只蚂蚁同时掉头，可以看作“两只蚂蚁交换编号”，继续向前移动，所以O（logn）的时间（排序）就可以算出最终在一个确定的位置有一个不确定编号的蚂蚁朝着一个确定的方向，求出每只蚂蚁的编号，可利用性质1

 

sort是个好东西。。

 

贴代码:

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,t;
struct ant{        
    int data;    //记录初始位置 
    int xb;        //记录蚂蚁编号 
    int fx;        //记录方向 
    int ans;    //记录最终位置 
} a[100010];
struct aaa{ 
    int data;
    int fx;
} b[100010];    //用于计算最终位置并按坐标大小排序，对应到a数组
bool cmp1(ant x,ant y)
{
    return x.data<y.data;
}
bool cmp2(aaa x,aaa y)
{
    return x.data<y.data;
}
bool cmp3(ant x,ant y)
{
    return x.xb<y.xb;
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
     {
         scanf("%d%d",&a[i].data,&a[i].fx);
         a[i].xb=i;
     }
    sort(a+1,a+1+n,cmp1);    //按坐标大小排序 
    for(int i=1;i<=n;i++)
     {
         b[i].data=a[i].fx==1?a[i].data+t:a[i].data-t;
         b[i].fx=a[i].fx;
     }
    sort(b+1,b+1+n,cmp2);    //按坐标大小排序
    for(int i=1;i<=n;i++)    //每只蚂蚁移动前后坐标次序不变 
    {
        a[i].ans=b[i].data;
        a[i].fx=b[i].fx;
    }
    for(int i=1;i<n;i++)
    if(a[i].ans==a[i+1].ans) a[i].fx=a[i+1].fx=0;        //若恰好正在转身，输出0 
    sort(a+1,a+1+n,cmp3); 
    for(int i=1;i<=n;i++)
    printf("%d %d
",a[i].ans,a[i].fx);
    return 0;
}