作者Fenikso (ばかちーは俺の嫁)
看板Prob_Solve
标题Re: [问题] SPOJ 1774. All Discs Considered [ALL]
时间Fri Oct 14 09:24:41 2011
※ 引述《AmosYang (Zzz...)》之铭言：
: 推 Fenikso:模拟一样是O(D)啊 不会比较慢 10/14 09:03
: 推 Fenikso:我回一篇好了.. 10/14 09:08
: → AmosYang: 能提示一下吗? :) 10/14 09:08
其实本质上是个dfs XD
1. 先建dependency graph (不是tree 虽然这不太重要XD)
这张图要用adjacency list存
对每个input (x, y) 从y连一条有向边到x
同时统计每个点的in degree
到这里为止是linear
以下假设先放第一片, 放第二片的时候同理
2. 把第一片中in degree是0的点抓出来放到一个array A1,
第二片中in degree是0的点抓出来放到一个array A2,
令i <- 1, 表示现在在光碟机里面的片子编号
(loop开始)
3. (Ai中所有歌听过一遍)
loop until Ai is empty:
对所有从点集Ai连出去的边{(x, y) | x \in Ai} 把y的in degree扣1
如果扣完发现y的in degree降到0, 则把y依编号放入A1或A2
4. (不见了XD)
5. 如果还有歌没听过, 则回到3. (换片)
i <- 3 - i
otherwise, break
6. 统计loop的次数就是答案.
因为每条边只碰到一次, 每个点最多碰到O(degree(v))次
所以整个loop是linear
--
--
※ 发信站 :批踢踢实业坊(ptt.cc)
◆ From: 118.169.226.206
※ 编辑: Fenikso 来自: 118.169.226.206 (10/14 09:25)
※ 编辑: Fenikso 来自: 118.169.226.206 (10/14 09:36)
1F：推 AmosYang: 感谢赐教 :D 10/14 09:33
※ 编辑: Fenikso 来自: 118.169.226.206 (10/14 09:37)
2F：→ AmosYang: 的确，这与我的作法一样都是 O(D)，但我的作法 10/14 09:48
3F：→ AmosYang: 对 memory 的需求应该会大一些 (用空间换时间) 10/14 09:48
4F：推 AmosYang: 我错了，我的作法比较慢 (晚了一天才想通 :D) 10/15 11:07