首页 > 其他 > 详细

51nod1548 欧姆诺姆和糖果

时间:2018-03-07 22:51:27      阅读:179      评论:0      收藏:0      [点我收藏+]

思路:

只有兩種糖果,枚舉其中一種糖果的數量就可以得到一個可行解;

但總有一種糖果的數量是較少的,並且該數量小於sqrt(C);

簡單證明:

1。若有任一糖果的質量大於sqrt(C),則必定有一糖果的數量小於sqrt(C);

2。若兩種糖果質量均小於sqrt(C),則可能存在兩種糖果數量均大於sqrt(C)的解,但對於這種情況,可以做如下轉換:

因爲兩種糖果質量均小於sqrt(C),則必定可以找到一個數公倍數K(K<C),然後將K全部用其中一種糖填滿,以達到總質量不變的情況下令較少的糖果數量小於sqrt(C)。

 

以上與最優解無關,但可以用sqrt(C)的時間複雜度枚舉出所有解的值,以得到最大值。

51nod1548 欧姆诺姆和糖果

原文:https://www.cnblogs.com/xiepingfu/p/8525306.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!