## 翻硬幣
問題描述
小明正在玩一個“翻硬幣”的游戲。
桌上放著排成一排的若干硬幣。我們用 * 表示正面,用 o 表示反面(是小寫字母,不是零)。
比如,可能情形是:**oo***oooo
如果同時翻轉左邊的兩個硬幣,則變為:oooo***oooo
現在小明的問題是:如果已知了初始狀態和要達到的目標狀態,每次只能同時翻轉相鄰的兩個硬幣,那么對特定的局面,最少要翻動多少次呢?
我們約定:把翻動相鄰的兩個硬幣叫做一步操作,那么要求:
輸入格式
兩行等長的字符串,分別表示初始狀態和要達到的目標狀態。每行的長度<1000
輸出格式
一個整數,表示最小操作步數。
樣例輸入1
******
o**o**
樣例輸出1
5
樣例輸入2
*o**o***o***
*o***o**o***
樣例輸出2
1
這道題啊,一道簡單的貪心題目,兩個字符串比較,如果發現不同,將當前和之后的翻到另一面,再繼續尋找。
~~~
#include <iostream>
#include <string>
using namespace std;
string str1,str2;
void fan(int n)
{
if(str1[n]=='*')
str1[n]='o';
else if(str1[n]=='o')
str1[n]='*';
if(str1[n+1]=='*')
str1[n+1]='o';
else if(str1[n+1]=='o')
str1[n+1]='*';
}
int main()
{
int i,len,sum;
while(cin>>str1>>str2)
{
sum=0;
len=str1.length();
for(i=0;i<len;++i)
if(str1[i]!=str2[i])
{
++sum;
fan(i);
}
cout<<sum<<endl;
}
return 0;
}
~~~
- 前言
- 入門訓練四道題
- 基礎練習之閏年判斷——BASIC-1
- 基礎練習之01字串——BASIC-2
- 基礎練習之字母圖形——BASIC-3
- 基礎練習之數列特征——BASIC-4
- 基礎練習之查找整除——BASIC-5
- 基礎練習之楊輝三角形——BASIC-6
- 基礎練習之特殊的數字——BASIC-7
- 基礎練習之回文數——BASIC-8
- 基礎練習之特殊回文數——BASIC-9
- 基礎練習之十進制轉十六進制——BASIC-10
- 基礎練習之十六進制轉十進制——BASIC-11
- 基礎練習之十六進制轉八進制——BASIC-12
- 基礎練習之數列排序——BASIC-13
- 算法訓練之區間K大數查詢——ALGO-1
- 算法訓練之最大最小公倍數——ALGO-2
- 藍橋杯-代碼填空之一
- 藍橋杯-代碼填空之二
- 藍橋杯-代碼填空之三
- 藍橋杯-代碼填空之精品
- 藍橋杯-歷屆試題之翻硬幣
- 藍橋杯-代碼填空之四
- 藍橋杯-結果填空題
- 藍橋杯-結果填空之排座位
- 藍橋杯-歷屆試題之大臣的旅費