[讨论] UVA 练习题 二分法和greedy

楼主: dedicationsh (ddd)   2016-02-25 13:01:11
大意是说先给定两个数m和k,
m表示资料个数,k表示将m个资料分为k份
找出最好的分法,使得max(每份的总和)有最小值
Sample Input
2 //总共两组数据
9 3 //9份资料 分3等份
100 200 300 400 500 600 700 800 900
5 4 //5份资料 分4等份
100 100 100 100 100
Sample Output
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
请问大家有什么想法吗
网络上是说用二分法和greedy
我不太清楚二分法是要用来找什么
greedy我不清楚他的意思,没修过data structure
附上连结:http://www.cnblogs.com/huaszjh/p/4705130.html
作者: Caesar08 (Caesar)   2016-02-25 13:45:00
greedy是一种算法,不是data structure
作者: suhorng ( )   2016-02-25 14:59:00
对答案m*做二分搜 greedy检查是否能分每段不超过m*
作者: Killercat (杀人猫™)   2016-02-27 12:05:00
greddy就是指“当下最好组合”,不过通常来讲greedy很难得到真正的最佳解要搭配其他的方法才比较容易得到最佳解
作者: KJFC (磁铁猫)   2016-03-02 08:29:00
从最小树的二分搜到另一个数 让他们的总和跟最大的数相差最小。不知道这样可不可以最小数恍神没看到二楼解答

Links booklink

Contact Us: admin [ a t ] ucptt.com