企业官网建设流程全解析

P1367 蚂蚁

网页链接

P1367 蚂蚁

题目描述

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

输入格式

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

第2 ∼ n + 1 2\sim n+12∼n+1行每行两个整数，第i + 1 i+1i+1行代表第i ii只蚂蚁的初始位置a i a_iai​及初始朝向b i b_ibi​（b i = 1 b_i=1bi​=1时蚂蚁朝右，b i = − 1 b_i=-1bi​=−1时蚂蚁朝左）。

输出格式

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

输入输出样例 #1

输入 #1

4 1 1 1 5 1 3 -1 10 1

输出 #1

2 0 6 1 2 0 11 1

说明/提示

数据范围及约定

• 对于40 % 40\%40%的数据，1 ≤ n ≤ 100 1\le n\le 1001≤n≤100；
• 对于80 % 80\%80%的数据，1 ≤ n ≤ 10 4 1\le n\le 10^41≤n≤104，0 ≤ t ≤ 1000 0\le t\le 10000≤t≤1000；
• 对于100 % 100\%100%的数据，n ≤ 10 5 n\le 10^5n≤105，0 ≤ t ≤ 10 5 0\le t\le 10^50≤t≤105，∣ a i ∣ ≤ 2 × 10 6 |a_i|\le 2\times 10^6∣ai​∣≤2×106。

解题思路

本题是经典蚂蚁碰撞问题的变形，核心利用碰撞等价于穿过的物理等价性，结合蚂蚁相对顺序不变的性质，通过两次排序高效求解，避免了逐帧模拟碰撞的高复杂度。

核心原理：

1. 碰撞等价性：两只蚂蚁迎面相向而行、相遇后掉头，等价于它们互相穿过对方、保持原朝向继续前进。由于蚂蚁无个体差异，最终所有蚂蚁的位置分布、朝向分布与真实场景完全一致。
2. 相对顺序不变：真实物理场景中蚂蚁仅掉头、不会穿透彼此，因此初始从左到右的蚂蚁排列顺序，t秒后仍然保持不变。

算法执行步骤：

1. 初始排序：将所有蚂蚁按初始位置从小到大排序，记录每只蚂蚁的原始编号，建立「原始编号 → 排序后序号」的映射关系。
2. 等价计算：按照“穿过模型”计算每只蚂蚁t秒后的位置与朝向，即位置更新为x + 朝向 × t，朝向暂时保持不变。
3. 终态排序：将计算后的蚂蚁再次按位置从小到大排序，得到最终的位置序列。根据相对顺序不变性，排序后的第i只蚂蚁，恰好对应初始排序后的第i只蚂蚁。
4. 相遇处理：遍历终态序列，若相邻两只蚂蚁位置相同，说明t时刻恰好相遇正在掉头，将两者朝向均设为0。
5. 结果映射：通过初始记录的映射关系，按原始编号顺序输出每只蚂蚁的最终位置与朝向。

算法总时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)，主要开销来自两次排序，完全适配n ≤ 10 5 n \le 10^5n≤105的数据规模。

总结

核心逻辑：利用碰撞等价于穿过的性质简化位置计算，结合相对顺序不变的特性还原每只蚂蚁的对应关系，最后处理恰好相遇的转向状态。
关键操作：两次排序锚定对应关系、原始序号映射、相邻位置重合判定转向状态。
效率保障：排序为主要开销，无需逐帧模拟碰撞，对数级复杂度即可处理十万级数据。

代码简要说明

1. 结构体定义：node存储蚂蚁的位置x、朝向d、原始编号num。
2. 初始排序与映射：读入所有蚂蚁信息后按位置升序排序，用pos数组记录每个原始编号对应的排序后下标，用于最终结果的映射还原。
3. 位置更新：按穿过模型计算每只蚂蚁t秒后的位置，朝向暂不修改。
4. 终态排序：再次按位置升序排列，得到最终的位置有序序列。
5. 相遇标记：遍历终态序列，若相邻蚂蚁位置相同，则将两者朝向均置为0，表示正在转向。
6. 结果输出：按原始编号顺序，通过pos数组定位对应蚂蚁的终态信息，逐行输出位置与朝向。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structnode{ll x,d,num;};node ant[100005];ll n,m,pos[100005];boolcmp(constnode&a,constnode&b){returna.x<b.x;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++){scanf("%lld%lld",&ant[i].x,&ant[i].d);ant[i].num=i;}sort(ant+1,ant+1+n,cmp);for(ll i=1;i<=n;i++){pos[ant[i].num]=i;ant[i].x+=ant[i].d*m;}sort(ant+1,ant+1+n,cmp);for(ll i=1;i<=n;i++)if(ant[i].x==ant[i+1].x)ant[i+1].d=ant[i].d=0;for(ll i=1;i<=n;i++)printf("%lld %lld\n",ant[pos[i]].x,ant[pos[i]].d);return0;}