中一小朋友，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 9n = 3 分成 3 组A) 分成 (1 2) (3 4) (5 6 7 8 9) -> max sum: 5+6+7+8+9=35B) 分成 (1 2 3) (4 5 6) (7 8 9) -> max sum: 7+8+9=24C) 分成 (1 2 3 4 5) (6 7) (8 9) -> max sum: 8+9=17D) ......
答案是 17，不管怎么分，最小的 max sum 是 17，C 的那种分法。
test case，取不同的 m, n, 并且 0 < m, n < 1000。不光看答案，也看运行时间。
暴力测试是可以的，但是运行时间超时 (AWS 上编译的 C++ 代码）。我觉得这样的题目给中一孩子太难了。而且也没弄懂怎么在上面应用 binary search。还是想得太复杂?
21 条回复
-
#1
划分型动态规划我瞎编的...
-
#2
这个题目没看懂1. 如果是有序数列，就不需要binary search，排序才需要
2. 不知道理解对不对，按照字面理解，既然至少需要两个数做group，找出最大两个数即可，然后计算和
3. 如果2理解是对的，而且是个无序数组，只要找出数组中两个最大的数字即可。算法很简单，一遍扫描就可以完成了，不需要binary search。
建议把英文原题贴出来吧，方便理解。 -
#3
没错，这题就是用binary search，dp也可以的。但time complexity是binary search好的
-
#4
两种解法1. binary search
在solution space暴力二分搜就好，时间复杂度m * lg n*(n+1)/2
2. dp
定义一个int [n][m], 从左到右遍历更新状态就好 -
#5
好像不是最大两个举个栗子 4 5 8 10 20. 分三组 20 就要一个数一组了
-
#6
我能想到的binary search是比如1<m,n<1000
首先这个答案最小是1，最大也就1到m和。宽泛一点无所谓。设S为1到m的和
然后看有没有分组满足答案为S/2的解，如果有，再看S/4，S/8，。。。开始binary sesrch
现在的问题变成，给定一个X，要看存不存在这样的n分组使得答案小于等于X。这问题其实不难：从1开始加，加到最接近X但是不超过X位置，分一组。再继续加，看最后的分组数是不是大于n就好。
不知道有没有说明白，可以站内信。 -
#7
说的真简介明了，solution space 二分法。就是！复杂度是n*log（数组的和）
-
#8
没什么时间，说下基本思路吧满足最小的最大group和，也就是说这种分法以内的所有的group和都比这个和小，在这个思路下用binary search, 先分一个，找到最大group sum, 之后所有的分法，只要遇到有group sum比这个大的，就可以丢弃，如果比这个小，那再继续比较下一段group sum,直到分完，有新的最小最大group sum的话就作为新的reference
-
#9
一句“之后所以的分发”，略去了C（m，n）的复杂度。和暴力法的复杂度在一个量级。
-
#10
你可以再仔细想想xmlzj
-
#11
这题就是递归搜索嘛从List开始iterate, 每个数要不就是包含在当前group, 要不就是在下一个group, 如果在下一group就把剩下的group-1
随便写的，不知道对不对，只测了楼主那个case是对的。原谅我放飞自我的魔性变量名
import sys
m = 9
n = 3
mylist = list(range(1, m+1))
my_dict = {} #可以memonize 省很多重复，只要记下参数和对应结果，懒得写了。。。
def min_max_sum(current, index, no_of_group):
print(current, index, no_of_group)
if(no_of_group==1):
return sum(mylist[index:])
elif (index == m-1):
if(no_of_group>1):
return sys.maxsize
else:
current.append(mylist[index])
max_sum_1 = max(min_max_sum([], index+1, no_of_group-1), sum(current))
max_sum_2 = min_max_sum(current, index+1, no_of_group)
return min(max_sum_1,max_sum_2)
print(min_max_sum([], 0, n)) -
#12
一粘贴代码全部gg,上个图
-
#13
[ThumbsUp][ThumbsUp][ThumbsUp]，就欣赏实干的！
-
3idiots 楼主#14
还是你们厉害，我的手艺不行了，惭愧。
-
3idiots 楼主#15
原题是个充满了各种诡异精灵名字的 problem solving 小故事。。。小朋友看得津津有味，我是费了半天的劲才从那堆不知所谓的名字里理清了它在问什么，然后归纳出了简单的描述。。。你有兴趣的话我回家去贴出来。。。现在教小朋友编程也要写成这种风格，真是开眼界。
-
3idiots 楼主#16
多谢啦。这么说我就懂了。原来是要从所有可能的 sum 里做 binary search，再凑有没有可能组成那个 sum。
-
3idiots 楼主#17
迷幻原题来了，大家欣赏一下。Barr the bear, Kang the Penquin, and Khang the car have just came back from another year of the internationally renowned programming competition, "I own iPads" (IOI), and have, as expected, come back with a shipment of N boxes of iPads, with the i-th box containing B_i iPads. Disembarking from the heavily laden cargo ship, the trio pounce/fly/jump from the ship onto solid ground, and make their way to a little-known resort, Tree Ville.
Despite Tree Ville being located in a desolate area far above the chimney tops, the perpetuators of evil, the Squidzofrenzic Calamari, an evil gang consisting of M squid, has found them!
After 23 hours of effort, the Squidzofrenzic Calamari finally managed to clip Kang's wings, force feed Khang with basic knowledge, and put Barr behind bars!
However, the Squidzofrenzic Calamari have agreed to let the IOI trio go, on one condition, that they sort out the mess of how to split the caches of iPads.
Being a very blur race, the Squidzofrenzic Calamari commander has demanded that the trio come up with a way to split the boxes of iPads among the horde of cephalopods, subject to the following conditions:
(i) To ensure equality, we wish to minimise the maximum number of iPads which any squid receives.
(ii) The amount of iPads in each box is indivisible, as the Squidzofrenzic Calamari are not in possession of machines capable of resealing the boxes, and iPads don't quite survive ten-mile underwater journeys very well.
(iii) To prevent further confusion, the boxes each squid gets must be consecutive (e.g. squid 6 gets boxes 17-42, but not boxes 17, 18, 20 etc.)
"What's this messy lousy formulation of a question. Just use a range tree..." Barr the bear growled and went to hibernate.
"This problem... tsk! Such a Tree Ville problem!" Kang the penquin quipped, and went into hiding in a freezer, never to be seen for the rest of the day.
Khang vanished mysteriously in search of free food after mysteriously saying something about fiascos.
And so, the Squidzofrenzic Calamari have thus an unresolved problem, and have consulted YOU to solve it for them.
Input
The first line of the input will contain two integers N and M (1 ≤ N, M ≤ 100,000).
The next line of the input will contain N integers, with the i-th integer representing B_i (1 ≤ B_i ≤ 1,000).
Output
The output should contain only one integer, representing the maximum number of iPads which any single squid receives.
Sample Input
9 3
1 2 3 4 5 6 7 8 9
Sample Output
17
Explanation for Sample Output
Dividing the iPads as such: 1 2 3 4 5 / 6 7 / 8 9 would fulfill the stipulated conditions, as any other division would increase number of iPads which the "luckiest" squid received. In this case, that squid is the third squid, which receives 17 iPads. -
#18
目测楼主可以考虑用空间来换取时间因为你说了m个自然数列
所有数列都可以认为是
1 2 3 4 5 6 7 ... M ＋ 某个数字B
B＝0即可
这个时候在做计算之前
你已经可以穷举出这M个数字所有连续n个数字之和形成一个新的矩阵
然后你懂的 -
3idiots 楼主#19
这是 python 吧？不太会，但是也能看。感觉和 暴力测试+重复sum的标记差不多，虽然递归看起来更简洁，但还是要遍历所有组合的。
-
3idiots 楼主#20
可能我描述有误，不是自然数列。按照原题来看，是任意数字的数列。
-
#21
并不是很暴力，因为有重复子问题，是动态规划主要是刚才不知道数组里的数字是整数。。。。。浮点数的话就只能这么做了。整数的话直接二分法就可以了，但是这里二分法的complexity是关于数字的和的，所以在数组小但是数字大的情况下比较慢，这个好像是dunjudge上的题。。。。