问码农们一个算法问题。

中一小朋友，competitive programming / binary search 内容中的一个练习题。简化一下问题描述：　
一个连续数列，比如 1 2 3 4 5 6 7 8 9 ... m 分成 n 个相连的 group，每种分法，取最大的那个 group sum。问，怎么分，才有最小的最大 group sum。
比如 m = 9, 1 2 3 4 5 6 7 8 9 n = 3 分成 3 组 A) 分成 (1 2) (3 4) (5 6 7 8 9) -> max sum: 5+6+7+8+9=35 B) 分成 (1 2 3) (4 5 6) (7 8 9) -> max sum: 7+8+9=24 C) 分成 (1 2 3 4 5) (6 7) (8 9) -> max sum: 8+9=17 D) ......
答案是 17，不管怎么分，最小的 max sum 是 17，C 的那种分法。
test case，取不同的 m, n, 并且 0 < m, n < 1000。不光看答案，也看运行时间。
暴力测试是可以的，但是运行时间超时 (AWS 上编译的 C++ 代码）。我觉得这样的题目给中一孩子太难了。而且也没弄懂怎么在上面应用 binary search。还是想得太复杂?

0 条评论

默认排序时间排序

2 个回答

单于和宁 2019-07-12 19:46

划分型动态规划
我瞎编的...

梅楠义 2019-07-12 19:46

这个题目没看懂
1. 如果是有序数列，就不需要binary search，排序才需要
2. 不知道理解对不对，按照字面理解，既然至少需要两个数做group，找出最大两个数即可，然后计算和
3. 如果2理解是对的，而且是个无序数组，只要找出数组中两个最大的数字即可。算法很简单，一遍扫描就可以完成了，不需要binary search。

建议把英文原题贴出来吧，方便理解。

问码农们一个算法问题。

2 个回答

相似问题