看板ACMCLUB
标 题Re: [问题] 数字环
发信站批踢踢兔 (Sat Jan 22 14:24:45 2005)
转信站ptt!Group.NCTU!grouppost
※ 引述《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