Re: [問題] 數字環
※ 引述《eric.bbs@ptt2.cc (認真的艾瑞克)》之銘言：
: ※ 引述《Freak1033 (I ain't gonna be ever17)》之銘言：
: : 先花 O(n) 統計所有數字的合, 接下來設定 tail 跟 head 指向第一個數字,
: : 若 tail 跟 head 間數字和大於全部的一半, 則 tail 往前走一步,
: : 否則 head 往前走一步, 每次更新 head 與 tail 間數字和需要常數時間,
: ^^^^^^^^
: 不知道是不是誤會你的意思了..
: 這裡最壞有可能是 O(n/2) ??
"更新數字和" O(1) 沒錯吧?
if(sum>...) {
sum-=num[tail];
tail=(tail+1)%n;
} else {
head=(head+1)%n;
sum+=num[head];
}
--
"聲音是聲音, icon 是 icon, 用 icon 來表示聲音的結果,
就是不知道哪個是聲音, 哪個是 icon. "
小光光
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.70.142.187
討論串 (同標題文章)