题目描述
在一个无限长的木板上有 n 只蚂蚁正在移动。蚂蚁按照从左到右的顺序从 1到 n 编号,每只蚂蚁都在一个与其他蚂蚁互不相同的位置上。
初始时,每只蚂蚁都有一个初始朝向:L 表示向左移动,R 表示向右移动,S 表示静止不动。每只蚂蚁的移动时的速度相同,然而在移动过程中部分蚂蚁之间会产生碰撞,在两只蚂蚁发生碰撞之后,都会停留在碰撞的位置无法再继续移动。所有蚂蚁不能改变它们的移动方向和状态。
现在给定所有蚂蚁的初始朝向,请你计算所有蚂蚁在木板上发生的碰撞总次数。碰撞次数按照一下方式计算:
①当两只移动方向相反的蚂蚁相撞时,碰撞次数加2;
②当一只移动的蚂蚁和一只静止的蚂蚁相撞时,碰撞次数加1。
案例代码
对于每只蚂蚁,我们只需将其位置和朝向存储在一个结构体中,然后遍历所有可能的碰撞情况进行计数即可。
具体步骤如下:
- 定义一个结构体Ant,包含两个属性:位置和朝向。
- 定义一个变量collisionCount,用于记录碰撞总次数,初始值为0。
- 定义一个变量n,表示蚂蚁的数量。
- 定义一个数组ants,用于存储所有蚂蚁的信息。
- 遍历数组ants,对于每只蚂蚁:
- 如果蚂蚁朝向为L,则将其位置减1,如果蚂蚁朝向为R,则将其位置加1。
- 如果蚂蚁和前一只蚂蚁朝向相反,则collisionCount加2。
- 如果蚂蚁和前一只蚂蚁朝向相同且前一只蚂蚁是静止的,则collisionCount加1。
- 返回collisionCount作为结果。
以下是用C++实现的案例代码:
#include <iostream>
#include <vector>
struct Ant {
int position;
char direction;
};
int countCollisions(std::vector<Ant>& ants) {
int collisionCount = 0;
for (int i = 1; i < ants.size(); i++) {
if (ants[i].direction == 'L') {
ants[i].position--;
} else if (ants[i].direction == 'R') {
ants[i].position++;
}
if (ants[i].direction != ants[i-1].direction) {
collisionCount += 2;
} else if (ants[i-1].direction == 'S') {
collisionCount++;
}
}
return collisionCount;
}
int main() {
int n;
std::cin >> n;
std::vector<Ant> ants(n);
for (int i = 0; i < n; i++) {
std::cin >> ants[i].direction;
ants[i].position = i + 1;
}
int collisionCount = countCollisions(ants);
std::cout << collisionCount << std::endl;
return 0;
}
输入示例:
5
L R R S L
输出示例:
3
解释:第一只蚂蚁向左移动,第二只和第三只蚂蚁向右移动,第四只蚂蚁静止不动,第五只蚂蚁向左移动。第一只和第四只蚂蚁发生碰撞,碰撞次数加1;第三只和第四只蚂蚁发生碰撞,碰撞次数加2。总共碰撞3次。
© 版权声明
本站资源来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。敬请谅解!
THE END