小猴编程周赛C++ | 蚂蚁碰撞问题案例代码

题目描述

在一个无限长的木板上有 n 只蚂蚁正在移动。蚂蚁按照从左到右的顺序从 1到 n 编号,每只蚂蚁都在一个与其他蚂蚁互不相同的位置上。
初始时,每只蚂蚁都有一个初始朝向:L 表示向左移动,R 表示向右移动,S 表示静止不动。每只蚂蚁的移动时的速度相同,然而在移动过程中部分蚂蚁之间会产生碰撞,在两只蚂蚁发生碰撞之后,都会停留在碰撞的位置无法再继续移动。所有蚂蚁不能改变它们的移动方向和状态。
现在给定所有蚂蚁的初始朝向,请你计算所有蚂蚁在木板上发生的碰撞总次数。碰撞次数按照一下方式计算:
①当两只移动方向相反的蚂蚁相撞时,碰撞次数加2;
②当一只移动的蚂蚁和一只静止的蚂蚁相撞时,碰撞次数加1。

案例代码

对于每只蚂蚁,我们只需将其位置和朝向存储在一个结构体中,然后遍历所有可能的碰撞情况进行计数即可。

具体步骤如下:

  1. 定义一个结构体Ant,包含两个属性:位置和朝向。
  2. 定义一个变量collisionCount,用于记录碰撞总次数,初始值为0。
  3. 定义一个变量n,表示蚂蚁的数量。
  4. 定义一个数组ants,用于存储所有蚂蚁的信息。
  5. 遍历数组ants,对于每只蚂蚁:
    • 如果蚂蚁朝向为L,则将其位置减1,如果蚂蚁朝向为R,则将其位置加1。
    • 如果蚂蚁和前一只蚂蚁朝向相反,则collisionCount加2。
    • 如果蚂蚁和前一只蚂蚁朝向相同且前一只蚂蚁是静止的,则collisionCount加1。
  6. 返回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
喜欢就支持一下吧
点赞5赞赏 分享