题解：学而思编程 蚂蚁碰撞

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：蚂蚁碰撞

【题目描述】

在一个无限长的木板上有n nn只蚂蚁正在移动。蚂蚁按照从左到右的顺序从1 11到n nn编号，每只蚂蚁都在一个与其他蚂蚁互不相同的位置上。

初始时，每只蚂蚁都有一个初始朝向：L LL表示向左移动，R RR表示向右移动，S SS表示静止不动。每只蚂蚁的移动时的速度相同，然而在移动过程中部分蚂蚁之间会产生碰撞，在两只蚂蚁发生碰撞之后，都会停留在碰撞的位置无法再继续移动。所有蚂蚁不能改变它们的移动方向和状态。

现在给定所有蚂蚁的初始朝向，请你计算所有蚂蚁在木板上发生的碰撞总次数。碰撞次数按照一下方式计算：

1. 当两只移动方向相反的蚂蚁相撞时，碰撞次数加2 22；
2. 当一只移动的蚂蚁和一只静止的蚂蚁相撞时，碰撞次数加1 11。

【输入】

一行一个字符串d i r dirdir，表示所有蚂蚁的初始朝向，保证d i r dirdir只包含L LL，R RR或S SS。

【输出】

一行一个整数，表示所有蚂蚁在木板上发生的碰撞总次数。

【输入样例】

RLRSLL

【输出样例】

5

【算法标签】

#字符串入门

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intcal(string s){intl=0,r=s.size()-1;// 左右指针// 去掉前缀的'L'while(l<=r&&s[l]=='L'){l++;}// 去掉后缀的'R'while(l<=r&&s[r]=='R'){r--;}intans=0;// 统计中间非'S'字符的个数for(inti=l;i<=r;i++){if(s[i]!='S'){ans++;}}returnans;}intmain(){string dir;cin>>dir;// 输入字符串cout<<cal(dir);// 输出计算结果return0;}

【运行结果】

RLRSLL 5