作者smartboy (小光光)
看板ACMCLUB
标题Re: [问题] 数字环
时间Sat Jan 22 19:21:17 2005
※ 引述《[email protected] (认真的艾瑞克)》之铭言：
: ※ 引述《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