Detail of message

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

我的方法（in），枚举+贪心。有点慢

Posted by xiaolonghingis at 2006-08-19 15:33:35 on Problem 2976
In Reply To:据说开始找比值最大的，每次找最优的和它合并可以过的，不知道能不能证明 Posted by:nuanran at 2006-08-19 14:45:21

因为答案c只可能在100到0之间，从大到小枚举c。假设答案为c，那么必然有                   
     100*(a1+.....+ak)
    -------------------- 〉=c ,两边同乘分母后得
       b1+.....+bk
    100*(a1+.....+ak)-c*(b1+.......+bk)>=0

    取100*ai-c*bi中最大的n-k个，看他们的和是否大于零即可。

Followed by:

如果你注意到这个方法的特点，你就会把枚举变成二分查找 (243) wywcgs 2006-08-19 15:53:01
Re:我的方法（in），枚举+贪心。有点慢 (254) madongtest 2006-08-20 02:18:37
那精度怎么处理？ (243) madongtest 2006-08-20 02:19:15
- 这里都是整数的运算，不用处理什么精度吧 (0) kevinew 2006-08-29 01:18:59
Re:这个方法倒不错，但是直接用这个方法编程，提交后就是Wrong，有一些细节需要注意。 (679) CCNUhaitun 2009-10-07 18:38:23
- 用这个方法精度很重要 (53) mysf 2010-07-29 19:46:36

Post your reply here:

Home Page Go Back To top