f651 - 開關燈
題目描述
題目要求計算將 n 個全亮的燈泡變成全暗狀態所需的最少操作次數。每次操作可以選擇一個燈泡改變狀態，同時其相鄰燈泡的狀態也會改變。
解題思路
觀察可以發現，每次操作一個燈泡，會影響到它自身和左右兩側的燈泡。為了將所有燈泡從亮變為暗，可以考慮每次操作影響的燈泡數量。
如果 n 可以被 3 整除，那麼每次操作三個燈泡可以將它們全部變成暗。 如果 n 除以 3 的餘數為 1，那麼需要操作 (n-1)/3 + 1 次。 如果 n 除以 3 的餘數為 2，那麼需要操作 (n-2)/3 + 1 次。
可以簡化為 (n-1)/3 + 1。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: 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(long long int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[10],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
long long int n;
while(n=read()){
write((n-1)/3+1);
putchar_unlocked('\n');
}
}