h989 - Waimai 超人與 Hehe 遊俠 (Easy Version)
題目描述
題目描述了 Waimai 超人與 Hehe 遊俠要計算最多可以同時使用的馬桶數量。給定一個包含 n 個馬桶狀態的陣列，其中 1 表示馬桶可用，0 表示馬桶正在被刷。如果一個馬桶正在被刷，或者它相鄰的馬桶有人正在使用，那麼其他人就不會使用這個馬桶。
解題思路
這題可以使用貪心策略來解決。我們從左到右遍歷馬桶，如果馬桶可用，則檢查其相鄰的馬桶是否可用。如果相鄰的馬桶可用，則將其標記為不可用，並將可用的馬桶數量加一。如果馬桶不可用，則跳過。
程式碼中，sum 變數追蹤連續可用馬桶的數量。當遇到不可用馬桶 (x == 0) 時，將 sum/2 + sum%2 加到 ans 上，然後重置 sum 為 0。sum/2 + sum%2 計算的是向上取整，因為每兩個連續的可用馬桶只能選一個。最後，在迴圈結束後，需要將剩餘的 sum 也計算進 ans 中，同樣使用 sum/2 + sum%2。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int n,ans,sum;
char x;
int main(){
n=read();
for(int i=0;i<n;++i){
x=read();
if(x==0){
ans+=sum/2+sum%2;
sum=0;
}
else{
++sum;
}
}
write(ans+sum/2+sum%2);
}