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

想法

Posted by digiter at 2009-02-07 23:49:52 on Problem 1062
"但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。"

设最优解中的最高等级是maxL, 最低等级是minL, 酋长是L[1],则一定有
L[1]属于区间[minL, maxL]且maxL - minL <= m
也就是最优解位于L[1]所在的某个m长度的区间内

枚举这些区间,因为在区间内的任意两点间都总是可达,不会有因为贪心策略而造成不可达的情况,所以可以用dijkstra

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