g*********s
发帖数: 1782 | 1 dp我看明白了，但怎么继续优化还没看懂。
二分法：
int lower = max{A_i}, upper = sum(A_i);
while (lower <= upper) {
// what should we do here?
} |
x******g
发帖数: 41 | 2 我的理解，
算mid
然后从用mid的值把sum的数组分段得到k_n
如果k_n>k，说明mid小了，在upper right重复搜索
反之在left搜索
比如
2 2 2 2 2 5 5 5 1 1 1 1 1
sum:2 4 6 8 10 15 20 25 26 27 28 29 30
lo = 5, hi = 30
mid = 17
17可以把sum数组分成2段，
2 4 6 8 10 15 20 | 25 26 27 28 29 30
所以17太大了，lo=5，hi=16
mid = 10
正好3段，结束 |
g*********s
发帖数: 1782 | 3
算mid
然后从用mid的值把sum的数组分段得到k_n
怎么个分段法？k_n是什么？
如果k_n>k，说明mid小了，在upper right重复搜索
反之在left搜索
比如
2 2 2 2 2 5 5 5 1 1 1 1 1
sum:2 4 6 8 10 15 20 25 26 27 28 29 30
lo = 5, hi = 30
mid = 17
17可以把sum数组分成2段，
2 4 6 8 10 15 20 | 25 26 27 28 29 30
这个分段怎么来的？和17有什么关系？
所以17太大了，lo=5，hi=16
mid = 10
正好3段，结束
【在 x******g 的大作中提到】
: 我的理解，
: 算mid
: 然后从用mid的值把sum的数组分段得到k_n
: 如果k_n>k，说明mid小了，在upper right重复搜索
: 反之在left搜索
: 比如
: 2 2 2 2 2 5 5 5 1 1 1 1 1
: sum:2 4 6 8 10 15 20 25 26 27 28 29 30
: lo = 5, hi = 30
: mid = 17
|
x******g
发帖数: 41 | 4 k_n是用这个mid的值把sum可以分成几个段
简单的方法就是从头开始扫描，
到sum值大于mid，记作一段
sum归零，继续扫描
看能得到几段，这个值就是k_n
【在 g*********s 的大作中提到】
:
: 算mid
: 然后从用mid的值把sum的数组分段得到k_n
: 怎么个分段法？k_n是什么？
: 如果k_n>k，说明mid小了，在upper right重复搜索
: 反之在left搜索
: 比如
: 2 2 2 2 2 5 5 5 1 1 1 1 1
: sum:2 4 6 8 10 15 20 25 26 27 28 29 30
: lo = 5, hi = 30
|
g*********s
发帖数: 1782 | 5 oh, then u can use lower/upper_bound instead of linear search.
it's upper_bound for sum > mid, or lower_bound for sum >= mid?
【在 x******g 的大作中提到】
: k_n是用这个mid的值把sum可以分成几个段
: 简单的方法就是从头开始扫描，
: 到sum值大于mid，记作一段
: sum归零，继续扫描
: 看能得到几段，这个值就是k_n
|
x******g
发帖数: 41 | 6 不是，mid分段扫描是linear的
二分是说找mid的值是二分的
所以复杂度是O(NlogM) N是数组的size，M是summation
大牛们correct me if i am wrong, thanks
【在 g*********s 的大作中提到】
: oh, then u can use lower/upper_bound instead of linear search.
: it's upper_bound for sum > mid, or lower_bound for sum >= mid?
|
g*********s
发帖数: 1782 | 7 what if the array elements are all non-negative?
【在 x******g 的大作中提到】
: 不是，mid分段扫描是linear的
: 二分是说找mid的值是二分的
: 所以复杂度是O(NlogM) N是数组的size，M是summation
: 大牛们correct me if i am wrong, thanks
|
