题目描述
有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在 $t$ 秒后的位置和朝向。
输入格式
第一行，两个空格隔开的整数 n,t（代表蚂蚁数 n 和时间 t.
第 2∼n+1 行每行两个整数，第 i+1行代表第 i只蚂蚁的初始位置 ai 及初始朝向 bibi（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%40% 的数据，1≤n≤1001≤n≤100；
- 对于 80%80% 的数据，1≤n≤1041≤n≤104，0≤t≤10000≤t≤1000；
- 对于 100%100% 的数据，n≤105n≤105，0≤t≤1050≤t≤105，∣ai∣≤106∣ai∣≤106。
解题思路（小tips）
本题的内在逻辑为若两只蚂蚁发生碰撞 两只蚂蚁的位置如何变化呢？
其实只要理解他们转头后 由于速度相同 所以两只蚂蚁的位置看作相互交换一次 即所有位置都是正确且一一对应的 只是具体的位置与下标序号不对应
理解以上思路就很简单了
首先 肯定要在结构体中记录下蚂蚁的实时位置和方向两个参数 其次 因为要按照输入顺序输出 所以还要记录下原始的输入顺序 最后 因为对撞后的位置发生了转换 不再与下标对应 所以需要找到其初始的相对位置
其余思路见代码注释
AC代码展示
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int x,y,num,w; //位置 方向 输入顺序 初始位置的顺序
}a[N];
bool cmp1(node p,node q){ //按照位置进行排序
return p.x<p.y;
}
bool cmp2(node p,node q){ //按照输入顺序进行排序
return p.num<p.num;
}
int n,m,res[N][2];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
a[i].num=i; //记录输入顺序
}
sort(a+1,a+1+n,cmp1); //行动前所有蚂蚁的位置 进行排序
for(int i=1;i<=n;i++){
a[i].w=i; //记录行动前蚂蚁位置的相对顺序
a[i].x+=a[i].y*m; //更新行动后的位置
}
sort(a+1,a+1+n,cmp1); //行动后蚂蚁位置的排序
for(int i=2;i<=n;i++) //位置重合则说明结束时正好转向
if(a[i].x==a[i-1].x) a[i].y=0,a[i-1].y=0;
for(int i=1;i<=n;i++){ //记录 行动后蚂蚁相对位置顺序 的值
res[i][0]=a[i].x;
res[i][1]=a[i].y;
}
sort(a+1,a+1+n,cmp2); //按照输入顺序排序
for(int i=1;i<=n;i++)
cout<<res[a[i].w][0]<<" "<<res[a[i].w][1]<<endl;
//最后按照输入顺序排序了一次 所以i已经是输入顺序了
//我只需要找到从每一个i在行动和两次排序后 到底存在了res中的哪个位置
//而输入时候的第几个蚂蚁 在排序完之后的相对位置顺序
//因为转一定会扭头 所以行动后排序完 第几个也还是第几个
//所以他第一开始在一群蚂蚁的起始位置中第几个 最后也还在第几个
return 0;
}