Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
此题数据不甚严谨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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator