b524 - 先別管這個了，你聽過yee嗎？

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個只包含 'y' 和 'e' 的字串，其中 'e' 的數量是 'y' 的兩倍。目標是計算將字串重新排列成 "yeeyeeyee..." 形式所需的最小交換次數。

解題思路

這個問題可以透過貪心演算法解決。由於 'e' 的數量是 'y' 的兩倍，目標字串的形式是 "yeeyeeyee..."，因此我們可以迭代字串，並將每個 'y' 移動到其應有的位置。對於每個 'y'，我們計算它與其目標位置之間的距離，並將這些距離加總起來。目標位置是 3 * y 的索引。

具體來說，我們維護一個 p 變數，表示下一個 'y' 的目標位置。當遇到 'y' 時，計算當前 'y' 的索引 i 與 p 之間的絕對差值，並將其加到答案 ans 中。然後，將 p 增加 3，以便為下一個 'y' 準備目標位置。

複雜度分析

• 時間複雜度: O(n)，其中 n 是字串的長度。我們需要遍歷字串一次。
• 空間複雜度: O(1)，我們只使用了幾個常數大小的變數。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
string s;
while(cin>>s){
int p=0,ans=0;
for(int i=0,sl=s.length();i<sl;i++)
if(s[i]=='y') {ans+=abs(i-p); p+=3;}
cout<<ans<<'\n';
}
}