Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:LTC's Solution

Posted by js05 at 2005-05-16 20:30:12
In Reply To:LTC's Solution Posted by:TN at 2005-05-16 20:21:32
> 
> B:An Old Stone Game
> 算法:贪心(经典问题),开始N个圆物品,每次合并两个和最小的且中间没有圆形物品的物品,变成一个方的物品。
> 详细介绍:本题我想到4种比较好的数据结构:
>           (1)fib堆 O(NLogN)
>           (2)二项堆 O(NLogN)
>           (3)左偏树 O(NLogN)
>           (4)普通堆+启发式合并 O(N(LogN)^2)
>         编程复杂度从难到易为(1)(2)(3)(4),出题者实现了(2)(3)(4)三种方法,程序运行速度从快到慢为(3)(2)(4)
> //单纯的贪心肯定是有问题的,例如N=4,个数分别为:5,3,4,5。
> 时间复杂度:O(NLogN)
> 难度:有一定难度
> 没有人通过。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator