a520 - 12416 - Excessive Space Remover
題目描述
題目要求計算將輸入字串中連續空白減少到最多一個空白所需的「全部取代」動作次數。一個動作定義為將兩個連續空白替換為一個空白。
解題思路
此題可以使用貪心演算法解決。我們遍歷字串，統計連續空白的數量。每次遇到連續空白結束（或到達字串末尾），如果連續空白數量大於 1，則需要執行一次「全部取代」動作，並更新最大連續空白數量。最終，所需的動作次數等於最大連續空白數量所需的「全部取代」次數，即 ceil(log2(max))。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的長度。因為我們需要遍歷字串一次。
- 空間複雜度: O(1)，因為我們只使用了常數額外的空間。
程式碼
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main(){
string a;
while(getline(cin,a)){
a+=' ';
int b=0,max=0;
bool c=0;
if(a[0]==' '){
b++;
c=0;
}
else
c=1;
for(int i=1;i<a.length();i++){
if(a[i]==' '||i==a.length()-1){
if(c==1){
if(b>max)
max=b;
b=0;
}
b++;
c=0;
}
else{
c=1;
}
}
if(max==0)
cout << 0 << endl;
else
cout << ceil(log2(max)) << endl;
}
}