a465 - 12405 - Scarecrow
題目描述
題目要求計算在一個由 '.' (良田) 和 '#' (不毛之地) 組成的 1 x N 的田地上，放置稻草人保護所有良田所需的最小稻草人數量。稻草人可以保護其自身以及左右緊鄰的格子。
解題思路
這題可以使用貪心演算法解決。遍歷田地，如果遇到良田 '.'，則在該位置放置稻草人 '#'，並保護其左右的格子。放置稻草人後，將該位置及其左右位置標記為已保護，避免重複計算。由於稻草人可以保護三個格子，因此每次遇到良田就放置稻草人可以保證使用最少的稻草人數量。
複雜度分析
- 時間複雜度: O(N) (N 是田地的長度，需要遍歷一次)
- 空間複雜度: O(N) (N 是田地的長度，用於儲存田地的字串)
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
int a,c;
string b;
cin >> a;
for(int i=1;i<=a;i++){
int count=0;
cin >> c;
cin >> b;
if(b[0]=='.'){
b[0]='#';
b[1]='#';
b[2]='#';
count++;
}
for(int i=1;i<c-1;i++){
if(b[i]=='.'){
b[i]='#';
b[i+1]='#';
b[i+2]='#';
count++;
}
}
if(b[c-1]=='.'){
count++;
}
cout <<"Case " << i <<": " << count << "\n";
}
}