※ 引述《Freak1033 (I ain't gonna be ever17)》之铭言： : ※ 引述《pangfeng (Liu)》之铭言： : : 一环上有n个正整数. 现将此环剪成两段, 要求两段上的数字合至多差一. : : 如何进行? : 先花 O(n) 统计所有数字的合, 接下来设定 tail 跟 head 指向第一个数字, : 若 tail 跟 head 间数字和大於全部的一半, 则 tail 往前走一步, : 否则 head 往前走一步, 每次更新 head 与 tail 间数字和需要常数时间, ^^^^^^^^ 不知道是不是误会你的意思了.. 这里最坏有可能是 O(n/2) ?? : 而我们可以保证 head 与 tail 都不会往前走超过 n 次, : 这样 amortized 分析起来, 全部的时间不会超过 O(n). : (赶在停电前打完, 有点乱... @_@) -- Eric Shang-Kuan (ericsk) Intelligent Space Lab.(Embedded Computing), Dept. of Computer Science & Information Engineering National Taiwan University --

※ 发信站: 批踢踢兔(ptt2.cc) ◆ From: 140.112.31.143