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

就是说|X1-Y1|+|X2-Y2|...的最大值必然是±(X1-Y1)±(X2-Y2)±...中的某一个

Posted by xfxyjwf at 2006-08-05 23:16:30 on Problem 2926
In Reply To:我也不是很懂 说的有点太简单了 Posted by:6233843 at 2006-08-05 23:09:45 
所以可以找到:
(X1+X2+...) 与 (Y1+Y2+...) 的差的最大值
(-X1+X2+...) 与 (-Y1+Y2+...) 的差的最大值
(X1-X2+...) 与 (Y1-Y2+...)  的差的最大值
...
...
答案就是这些最大值里最大的那一个
至于(X1+X2+...) 与 (Y1+Y2+...) 的差的最大值,O(N)就可以求出来
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