首页 > 试题广场 >

坠落的蚂蚁

[编程题]坠落的蚂蚁

热度指数：8955 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘（0或100厘米处）则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即1，2，3，…99厘米），有且只有一只蚂蚁A速度为0，其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁A从此时刻到坠落所需要的时间。

输入描述:

    第一行包含一个整数表示蚂蚁的个数N（2<=N<=99），之后共有N行，每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数P（1<=P<=99），第二个数字表示初始方向,-1表示向左，1表示向右，0表示静止。

输出描述:

    蚂蚁A从开始到坠落的时间。若不会坠落，输出“Cannot fall!”

示例1

输入

输出

算法知识视频讲解

csyfZhang

发表于 2020-04-24 11:57:06

图解坠落的蚂蚁https://blog.csdn.net/csyifanZhang/article/details/105726123↑更好的阅读体验思路分析首先我们需要明确一点， 0次碰撞时，其速度本身就为0，2次碰撞是什么情况呢？经过两次碰撞之后，A会再次装上右侧的速度为0的蚂蚁，他的速展开全文

夜尽天明AR

发表于 2021-01-22 18:54:34

关于“坠落的蚂蚁”这道题。一开始我尝试用追踪记录每一只蚂蚁的状态的方法解题，代码写了很长，最后只有40%的用例通过了检验，折腾了半天我也没发现到底错误在什么地方。代码：https://paste.ubuntu.com/p/q3GCtB2fw4/ 这道题的一种简单思路如下：1.静止蚂蚁的位置是固定不变展开全文

牛客652687585号

发表于 2022-01-24 14:03:47

1.蚂蚁之间不能互相穿过，因此各个蚂蚁的相对位置不变。 2.各个蚂蚁除了速度和位置，其余是无差别的，因此两个蚂蚁相撞可以等效为这两个蚂蚁互相穿过，并交换无差别的“躯壳”。 3.可以假设各个蚂蚁相互独立，不会相撞，可以分别得出每个蚂蚁坠落的时间和方向。 4.每当有一个蚂蚁从左边坠落，展开全文

稻草人哦

发表于 2024-01-12 19:53:25

#include <iostream> using namespace std; #include<stdio.h> #include<stdlib.h> typedef struct ANTs { int address; int speed; int 展开全文

福音骑士

发表于 2023-06-23 19:51:04

#include <bits/stdc++.h> using namespace std; // bugs存放位置i下的初始虫子速度 int bugs[120]; // lefts是在速度为0的虫子左边的向右移动的虫子下标索引数组 vector<int> lefts; // 展开全文

wbc990512

发表于 2021-02-08 21:49:17

一开始想着写个大循环，按照时间每0.5秒增加来算，实在是写不懂了，去看评论区发现还是需要画图琢磨一下各种情况，是有规律的。。借用大佬@想吃芒果冰啊的思路和@183610班曲超的代码，整理一下思路。0、除A以外的其他蚂蚁，因为改变方向在感官看起来相当于擦肩而过，所以假设它们相遇不交换速度。1、由于展开全文