1
Xe0n0 2013-07-25 22:20:41 +08:00 1
一维数轴上情况,相当于四个连续区间中最小区间长度最大。二分查找这个最小区间的长度,从数范围的四分之一开始二分。
每一次检验其实只有中间三个点需要尝试,最小和最大值都可以分别固定为数列的最小值和最大值,因为这不会比最优解更差。 因为数是正太分布的,所以区间移动的时候会跳过中间更多的点。应该比平均分布收敛得更快。我是这么觉得的。 |
2
binux 2013-07-25 22:33:57 +08:00 1
_list = sorted([11356, 51308, 56246, 58316, 65360, 69866, 74806, 80104, 99488, 106486, 110695, 131901, 170195])
a = [0, 1, 2, len(_list)-2, len(_list)-1] max_a = None max_d = 0 while a[1] < a[2] < a[3]: _ a2_max_d = 0 _ #find pos for a[2] _ while a[2] < a[3]: __ a2_max_d = max(a2_max_d, min(_list[a[2]]-_list[a[1]], _list[a[3]]-_list[a[2]])) __ a[2]+=1 _ tmp_min_d = min(_list[a[4]]-_list[a[3]], _list[a[1]]-_list[a[0]], a2_max_d) _ if tmp_min_d > max_d: __ max_d = tmp_min_d __ max_a = list(a) _ #move a1 or a3 _ if _list[a[4]]-_list[a[3]] > _list[a[1]]-_list[a[0]]: __ a[1]+=1 __ a[2]=a[1]+1 _ else: __ a[3]-=1 __ a[2]=a[1]+1 print [_list[x] for x in a], max_d |
4
ThunderEX OP |
5
binux 2013-07-25 23:17:35 +08:00 1
@ThunderEX 有些细节错误
_list = sorted([11356, 51308, 56246, 58316, 65360, 69866, 74806, 80104, 99488, 106486, 110695, 131901, 170195]) a = [0, 1, 2, len(_list)-2, len(_list)-1] max_a = None max_d = 0 while a[1] < a[2] < a[3]: _ a2_max_d = 0 _ a2_pos = a[2] _ #find pos for a[2] _ while a[2] < a[3]: __ if a2_max_d < min(_list[a[2]]-_list[a[1]], _list[a[3]]-_list[a[2]]): ___ a2_pos = a[2] ___ a2_max_d = min(_list[a[2]]-_list[a[1]], _list[a[3]]-_list[a[2]]) __ a[2]+=1 _ tmp_min_d = min(_list[a[4]]-_list[a[3]], _list[a[1]]-_list[a[0]], a2_max_d) _ if tmp_min_d > max_d: __ a[2] = a2_pos __ max_d = tmp_min_d __ max_a = list(a) _ #move a1 or a3 _ if _list[a[4]]-_list[a[3]] > _list[a[1]]-_list[a[0]]: __ a[1]+=1 __ a[2]=a[1]+1 _ else: __ a[3]-=1 __ a[2]=a[1]+1 print [_list[x] for x in max_a], max_d |
7
kuphrer 2013-07-25 23:36:28 +08:00
动态规划
|
8
juicy 2013-07-25 23:51:37 +08:00
"这5个数的任意两两之差的最小值尽可能大"+这5个数已排序
<====> 第5个数与第1个数的差值最大? 那就是说循环求出第5个和第1个,第6个和第2个,第7个和第3个,...的差值,比较一下哪个最大就行了?只有O(n)的复杂度。。即使是没排序的,通过merge sort,也能达到O(nlogn)的效率。。 不知道我这样理解对不对。。是不是想简单了?。。。 |
9
juicy 2013-07-26 00:01:10 +08:00 1
汗。。。第一条就不成立。。。我说怎么会这么简单。。。太冒失了。。。。。
|