P1367 蚂蚁【洛谷算法习题】

P1367 蚂蚁网页链接P1367 蚂蚁题目描述有许多蚂蚁在一根无限长的木棍上每一只蚂蚁都有一个初始位置和初始朝向任意两只蚂蚁的初始位置不同。蚂蚁们以每秒一个单位的速度向前移动当两只蚂蚁相遇时它们会掉头掉头时间忽略不计。现给出每只蚂蚁的初始位置和初始朝向请你计算出它们在t tt秒后的位置和朝向。输入格式第一行两个空格隔开的整数n , t n,tn,t代表蚂蚁数n nn和时间t tt。第2 ∼ n 1 2\sim n12∼n1行每行两个整数第i 1 i1i1行代表第i ii只蚂蚁的初始位置a i a_iai​及初始朝向b i b_ibi​b i 1 b_i1bi​1时蚂蚁朝右b i − 1 b_i-1bi​−1时蚂蚁朝左。输出格式共n nn行每行两个整数第i ii行代表t tt秒后第i ii只蚂蚁的位置及朝向− 1 -1−1表示朝左1 11表示朝右0 00表示正在转向中。输入输出样例 #1输入 #14 1 1 1 5 1 3 -1 10 1输出 #12 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≤1040 ≤ t ≤ 1000 0\le t\le 10000≤t≤1000对于100 % 100\%100%的数据n ≤ 10 5 n\le 10^5n≤1050 ≤ 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。解题思路本题是经典蚂蚁碰撞问题的变形核心利用碰撞等价于穿过的物理等价性结合蚂蚁相对顺序不变的性质通过两次排序高效求解避免了逐帧模拟碰撞的高复杂度。核心原理碰撞等价性两只蚂蚁迎面相向而行、相遇后掉头等价于它们互相穿过对方、保持原朝向继续前进。由于蚂蚁无个体差异最终所有蚂蚁的位置分布、朝向分布与真实场景完全一致。相对顺序不变真实物理场景中蚂蚁仅掉头、不会穿透彼此因此初始从左到右的蚂蚁排列顺序t秒后仍然保持不变。算法执行步骤初始排序将所有蚂蚁按初始位置从小到大排序记录每只蚂蚁的原始编号建立「原始编号 → 排序后序号」的映射关系。等价计算按照“穿过模型”计算每只蚂蚁t秒后的位置与朝向即位置更新为x 朝向 × t朝向暂时保持不变。终态排序将计算后的蚂蚁再次按位置从小到大排序得到最终的位置序列。根据相对顺序不变性排序后的第i只蚂蚁恰好对应初始排序后的第i只蚂蚁。相遇处理遍历终态序列若相邻两只蚂蚁位置相同说明t时刻恰好相遇正在掉头将两者朝向均设为0。结果映射通过初始记录的映射关系按原始编号顺序输出每只蚂蚁的最终位置与朝向。算法总时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)主要开销来自两次排序完全适配n ≤ 10 5 n \le 10^5n≤105的数据规模。总结核心逻辑利用碰撞等价于穿过的性质简化位置计算结合相对顺序不变的特性还原每只蚂蚁的对应关系最后处理恰好相遇的转向状态。关键操作两次排序锚定对应关系、原始序号映射、相邻位置重合判定转向状态。效率保障排序为主要开销无需逐帧模拟碰撞对数级复杂度即可处理十万级数据。代码简要说明结构体定义node存储蚂蚁的位置x、朝向d、原始编号num。初始排序与映射读入所有蚂蚁信息后按位置升序排序用pos数组记录每个原始编号对应的排序后下标用于最终结果的映射还原。位置更新按穿过模型计算每只蚂蚁t秒后的位置朝向暂不修改。终态排序再次按位置升序排列得到最终的位置有序序列。相遇标记遍历终态序列若相邻蚂蚁位置相同则将两者朝向均置为0表示正在转向。结果输出按原始编号顺序通过pos数组定位对应蚂蚁的终态信息逐行输出位置与朝向。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structnode{ll x,d,num;};node ant[100005];ll n,m,pos[100005];boolcmp(constnodea,constnodeb){returna.xb.x;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,m);for(ll i1;in;i){scanf(%lld%lld,ant[i].x,ant[i].d);ant[i].numi;}sort(ant1,ant1n,cmp);for(ll i1;in;i){pos[ant[i].num]i;ant[i].xant[i].d*m;}sort(ant1,ant1n,cmp);for(ll i1;in;i)if(ant[i].xant[i1].x)ant[i1].dant[i].d0;for(ll i1;in;i)printf(%lld %lld\n,ant[pos[i]].x,ant[pos[i]].d);return0;}