小明正在玩一個“翻硬幣”的游戲。

? ? 桌上放著排成一排的若干硬幣。我們用 * 表示正面，用 o 表示反面（是小寫字母，不是零）。

? ? 比如，可能情形是：**oo***oooo
? ??
? ? 如果同時翻轉左邊的兩個硬幣，則變為：oooo***oooo

? ? 現在小明的問題是：如果已知了初始狀態和要達到的目標狀態，每次只能同時翻轉相鄰的兩個硬幣,那么對特定的局面，最少要翻動多少次呢？
? ? 我們約定：把翻動相鄰的兩個硬幣叫做一步操作，那么要求：
? ?
程序輸入：
兩行等長的字符串，分別表示初始狀態和要達到的目標狀態。每行的長度<1000

程序輸出：
一個整數，表示最小操作步數

例如：
用戶輸入：
**********
o****o****

程序應該輸出：
5

再例如：
用戶輸入：
*o**o***o***
*o***o**o***

程序應該輸出：
1

---

題目分析：這個題目一開始我想直接bfs，然后剪一下枝就行了吧，雖然輕輕松松把樣例過掉了，但是畢竟每一個狀態都能擴展出最多500種狀態，所以一旦答案比較多(大于10)然后就爆掉了。。所以這個題目肯定不能用搜索了

當然正解肯定不會那么復雜，只需要貪心一下就行了，因為每次需要翻兩個相鄰的硬幣，所以如果兩個狀態可以互相到達的話，那么這兩個字符串中不相同的位置一定是偶數個，這樣我們就可以兩兩匹配，貪心的原則肯定是讓相鄰兩個不同的位置匹配就好了，具體我也不太會證明，不過顯然是正確的。。

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<int>pos;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);string a,b;cin>>a>>b;for(int i=0;i<a.size();i++)if(a[i]!=b[i])pos.push_back(i);int ans=0;for(int i=0;i<pos.size();i+=2)ans+=pos[i+1]-pos[i];cout<<ans<<endl;return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的蓝桥杯 - 翻硬币(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。