看板ACMCLUB
标 题Re: [问题] 数字环
发信站批踢踢兔 (Sat Jan 22 00:01:12 2005)
转信站ptt!Group.NCTU!grouppost
※ 引述《pangfeng (Liu)》之铭言：
: 一环上有n个正整数. 现将此环剪成两段, 要求两段上的数字合至多差一.
: 如何进行?
先花 O(n) 统计所有数字的合, 接下来设定 tail 跟 head 指向第一个数字,
若 tail 跟 head 间数字和大於全部的一半, 则 tail 往前走一步,
否则 head 往前走一步, 每次更新 head 与 tail 间数字和需要常数时间,
而我们可以保证 head 与 tail 都不会往前走超过 n 次,
这样 amortized 分析起来, 全部的时间不会超过 O(n).
(赶在停电前打完, 有点乱... @_@)
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.109.224.64