看板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