算法题

bd

是均分么。。 如果是均分排序就好。。。

有个思路 但是不知道对不对 假设你对n-1个数有了一个正确的分组方案，那么这时你得到了新的一个数，如何调整分组才能使这个分组方案依然是最优的？ 假设新得到的数t属于其中的某分组的某个区间，那结果显然不会变，直接把新来的丢进去就行了 假设不属于，那么当前的分组数是否小于K，如果小于，那新来的数t自己一组，否则需要调整分组 调整的方案就是对于每个分组[a, b]（a和b分别表示最小和最大的两个数），比较t与a和b的差，找出所有分组中差的绝对值最小的符合条件的a或b，然后替换，并更新结果 但是我不能证明这个思路是正确的 如果正确，实现方案就很好说了，首先判断n是否小于等于k，如果是直接返回0 否则准备一个k*2大小的数组，然后将前k个数排序，并每个数两次的形式放入数组，如 a, a, b, b, c, c, d, d... （a < b < c < d） 表示当前分组方案为[a, a][b, b][c, c][d, d]...，即前k个数独自一组，即结果为0 然后开始考虑第k+1个数，以二分查找的形式找到它所属的位置，并按照上面说的更新分组方案，直到考虑完全部的n个数 时间复杂度nlogn

考虑选出来的两组最大最小值，按大小排序为a1，a2，a3,a4，可以证明分组为a1,a2和a3,a4时是最优的。所以最优解应该是将数组排序之后按顺序切成K份，用DP应该可以解。

n和k不确定，无法保证均分，而且均分也不一定使和最小 【 在 a940100079 (一笑一蹙) 的大作中提到: 】 : 是均分么。。 : 如果是均分排序就好。。。

我觉得这个方法有两个问题，不知道是不是我理解不对。 1.新得到的数t可能全部或大部分属于前面的区间，直接丢进去会导致最终不够k个组 2.新得到的数t如果与前面的组（a，b）分裂成（a，t）和（t，b），得到的和有可能小于（a，b） 【 在 Nroskill (Nroskill) 的大作中提到: 】 : 有个思路 但是不知道对不对 : 假设你对n-1个数有了一个正确的分组方案，那么这时你得到了新的一个数，如何调整分组才能使这个分组方案依然是最优的？ : ...................

均分不一定是最优解，举个例子：1，100，101，102。分成2组，显然1为一组，100.101.102为一组才是解。 【 在 hxidkd ([意涵团]djdjid) 的大作中提到: 】 : 考虑选出来的两组最大最小值，按大小排序为a1，a2，a3,a4，可以证明分组为a1,a2和a3,a4时是最优的。所以最优解应该是将数组排序之后按顺序切成K份，用DP应该可以解。

没说均分啊，我是指按顺序切分，前一组的数都不大于后一组的。 【 在 daboluo 的大作中提到: 】 : 均分不一定是最优解，举个例子：1，100，101，102。分成2组，显然1为一组，100.101.102为一组才是解。

哦哦，不过这样复杂度是不是相当于暴力算法 【 在 hxidkd ([意涵团]djdjid) 的大作中提到: 】 : 没说均分啊，我是指按顺序切分，前一组的数都不大于后一组的。