题目：https://codeforces.ml/problemset/problem/1392/D
题意 【【题解】Codeforces Global Round 10 -- D】n个人站成一圈，每个人有一个朝向（L或R）。每次操作可以改变一个人的朝向。输入每个人初始的朝向，输出至少经过多少次操作，使得任何三个位置连续的人朝向不全相同。
题解 首先 n <= 2 时输出0即可。
若 n >= 3，
首先拆环为链。将连续且朝向相同的人分为一块，最后得到若干块。设每块的长度为len，则每块隔两个人改变一个，需要进行的操作次数为len / 3。注意如果首尾两端朝向相同，则要合并为一块。
还要注意的是：如果所有人的朝向相同，那么需要进行的操作次数为(n+2) / 3。具体细节看代码吧。
#include
using namespace std;
int t, n, ans;
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--){
ans = 0;
cin >> n >> s;
bool first = 0;
// 首段单独判断
int len = 1, fl = 0;
// fl为链中首端一块的长度
for (int i = 1;
i < n;
i++)
if (s[i] == s[i-1]) len++;
else{
if (!first)
fl = len, first = 1;
else ans += len / 3;
len = 1;
}
if (!first) {// 表示所有字母是相同的，构成一个环
cout << (n <= 2 ? 0 : (n+2)/3) << endl;
}
else{
if (s[0] == s[n-1])
cout << ans + (fl+len) / 3 << endl;
else
cout << ans + fl / 3 + len / 3 << endl;
}
}
return 0;
}
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络