![](http://image109.360doc.com/DownloadImg/2020/08/1717/199547253_1_20200817051559240)
背景这段时间,LSGO软件技术团队的一个小组在准备明年3月份蓝桥杯的比赛。 我把他们写的算法题目转发过来,为其他准备蓝桥杯比赛的同学做个参考啊。 完成题目
题目问题描述 小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。比如,可能情形是:oo*oooo 如果同时翻转左边的两个硬币,则变为:oooo***oooo 现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢? 我们约定:把翻动相邻的两个硬币叫做一步操作,那么要求: 输入格式 两行等长的字符串,分别表示初始状态和要达到的目标状态。每行的长度 < 1000 输出格式 一个整数,表示最小操作步数。 样例输入 ********** o****o****
样例输出 5
样例输入 *o**o***o*** *o***o**o***
样例输出 1
代码实现#include <iostream> #include <string>
using namespace std;
int main() { // 一种贪心法,自前向后,不同就翻 int cnt = 0; string s1, s2; cin >> s1 >> s2; for (int i = 0; i < s1.length(); i++) if (s1[i] != s2[i]) { s1[i] = s1[i] == 'o' ? '*' : 'o'; s1[i+1] = s1[i+1] == 'o' ? '*' : 'o'; ++cnt; } cout << cnt; return 0; }
int main() { // 每两个不同位置的距离 int cnt = 0, t = 0; int pos[1000]; string s1, s2; cin >> s1 >> s2;
for (int i = 0; i < s1.length(); i++) if (s1[i] != s2[i]) { pos[t++] = i; }
for (int i = 1; i < t; ++i) cnt += pos[i] - pos[i-1]; cout << cnt; return 0; }
参考文献
|