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

Re:这个方法倒不错，但是直接用这个方法编程，提交后就是Wrong，有一些细节需要注意。

Posted by CCNUhaitun at 2009-10-07 18:38:23 on Problem 2976
In Reply To:我的方法（in），枚举+贪心。有点慢 Posted by:xiaolonghingis at 2006-08-19 15:33:35

因为答案c只可能在100到0之间，从大到小枚举c。假设答案为c，那么必然有                   
      100*(a1+.....+ak)
     -------------------- 〉=c ,两边同乘分母后得
        b1+.....+bk
     100*(a1+.....+ak)-c*(b1+.......+bk)>=0
     取100*ai-c*bi中最大的n-k个，看他们的和是否大于零即可。 

     直接使用这个方法不能处理进位。假如
      100*(a1+.....+ak)
     -------------------- =85.6 ,  用这个方法算出的答案是85，实际上答案是86，因为
        b1+.....+bk
      100*(a1+.....+ak)-86*(b1+.......+bk)<0
     所以：
      1000*(a1+.....+ak)
     -------------------- 〉=c , 那么c是在0到1000之间，两边同乘分母后得
        b1+.....+bk
     1000*(a1+.....+ak)-c*(b1+.......+bk)>=0
     取1000*ai-c*bi中最大的n-k个，看他们的和是否大于零即可。 
     用二分的方法来枚举c，如果满足上述条件最大的c是ans，那么最后要输出（ans+5）/10，这样就可以处理进位。