C++ 齿轮问题：静态数组解法 - GearsDiv2 - 常规

C++ 齿轮问题：静态数组解法 - GearsDiv2

问题描述

Goose Tattarrattat 有一台机器包含 n 个齿轮（编号 0 到 n-1），这些齿轮排成一个环，两个啮合的齿轮必须同时反向转动。给出每个齿轮要求的转动方向，你需要找到最少需要删除多少个齿轮才能满足所有齿轮的转动方向要求。

输入格式

第一行，一个正整数 n，表示齿轮数量。
第二行，一个长度为 n 的字符串，表示每个齿轮的方向，'L' 表示逆时针，'R' 表示顺时针。

输出格式

一个整数，表示最小需要删除的齿轮个数。当一个齿轮删除了之后，其他齿轮还在原来的位置，因此与它相邻的两个齿轮不再由它连接。

输入输出样例

GearsDiv2.in	GearsDiv2.out
4	1
LRRR
3	2
RRR
4	0
LRLR
16	6
LRLLRRLLLRRRLLLL
50	14
RRRRRRRLRRRRRRRLRLRLLRLRLRLRRLRLRLLLRLRLLRLLRRLRRR

数据规模和约定

3 <= n <= 50

解题思路

首先，我们需要确定每个齿轮的转动方向是否满足要求。如果有相邻的两个齿轮转动方向相同，则需要删除其中一个齿轮。

我们可以用一个静态数组来保存每个齿轮的转动方向，并用一个变量 count 来记录需要删除的齿轮数量。

然后，我们遍历每个齿轮，判断它与相邻齿轮的转动方向是否相同。如果相同，则需要删除其中一个齿轮，count 加 1。

最后，我们输出 count 的值即为最小需要删除的齿轮数量。

C++ 代码实现如下：

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    string directions;
    cin >> directions;
    
    char gears[50];
    for (int i = 0; i < n; i++) {
        gears[i] = directions[i];
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (gears[i] == gears[(i + 1) % n]) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

复杂度分析：

时间复杂度为 O(n)，其中 n 为齿轮数量。
空间复杂度为 O(n)，需要额外的数组来保存每个齿轮的转动方向。