1208. 翻硬币
题目描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。
比如,可能情形是:**oo***oooo
如果同时翻转左边的两个硬币,则变为:oooo***oooo
现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串,分别表示初始状态和要达到的目标状态。
输出格式
一个整数,表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1:
**********
o****o****
输出样例1:
5
输入样例2:
*o**o***o***
*o***o**o***
输出样例2:
1
算法
模拟/递推之开关问题
-
从前往后依次比较
st[i]
和ed[i]
-
通过这种顺序枚举灯泡,可以保证每个灯泡的状态只会受一个开关影响
-
如果
st[i] != ed[i]
,则将st[i]
和st[i + 1]
反转 -
由于题目保证一定有解,所以只需要比较前
n - 1
个字符
如何保证操作次数最小呢?
-
每个开关最多只会被按一次
-
在上面的前提下,从前往后依次枚举,每个开关按不按是唯一确定的,最多只有一组解或者无解(最后一个灯泡是否一致),但是此题保证数据一定有解
拓展
- 每次只能同时翻转相邻的 3/4/… 个硬币,上面的做法也是可以的
视频讲解:蓝桥杯C++ AB组辅导课——2.1 二分与前缀和——00:02:20
时间复杂度
$O(n)$
代码
#include <iostream>
#include <cstring>
const int N = 105;
char st[N], ed[N];
void turn(int i)
{
if(st[i] == 'o')
st[i] = '*';
else
st[i] = 'o';
}
int main()
{
scanf("%s%s", st, ed);
int res = 0;
// 数据保证答案一定有解,因此 st[] 和 ed[] 的长度一定相等
int n = strlen(st);
// 数据保证答案一定有解,因此只需要比较前 n - 1 个字符,最后一个字符一定是相等的
for(int i = 0; i < n - 1; i++)
{
if(st[i] != ed[i])
{
turn(i), turn(i + 1);
res++;
}
}
printf("%d", res);
return 0;
}