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 saintqdd at 2011-04-21 13:51:09 on Problem 3404
3 6 8 10
5 6 8 10

贪心中一条是,如果d[0]+d[i-1]>=2*d[1]的时候,才挪最大的两个
否则,还是用最小的挪最大的。

我起初使用的是d[i-1]>d[1]的时候这个条件,发现也过了,。。。。。!!!!!!!!

对于5 6 8 10,
最佳是   6  5 10 6 6
只用对小的10 5 8  5 6
可见,8+5>6+6,这说明了刚才那个条件的成立

现在换成 3 6 8 10
最佳   6 3 10 6 6 
只最小 10 3 8 3 6
可见, 8+3<6+6,所以最佳的选择错了。

原因是d[i-1]>d[1]这个条件不足以保证结果最优,真正的条件是 d[0]+d[i-1]>=2*d[1]. 

个人见解

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