求最窄区间的算法，其中m将覆盖一组数字。
假设您有一个n数的列表。您可以选择m整数(让我们将整数称为)。对于每一个整数a，删除包含在a，a+ x范围内的每个数字，其中 x 是一个数字。可以清除列表的x的最小值是多少？
例如，如果您的数字列表是
1 3 8 10 18 20 25
M= 2，答案是x= 5。
您可以选择两个整数5和20，这将清除列表，因为它删除了5-5，5+5和20-5，20+5中的所有数字。
我该怎么解决这个问题？我认为解决方案可能与动态规划有关。我不想要蛮力法的解决方案。
代码将非常有用，最好是用Java、C++或C语言编写。
回答 5
Stack Overflow用户
发布于 2016-01-16 11:40:11
递归解决方案：
首先，你需要一个估计，你可以分裂成m个群，然后估计(X)必须是~()/ 2*m，估计的(X)可以是一个解。如果有更好的解决方案，那么在所有组中，它的x都低于extimated(x)！您可以用第一组检查它，然后递归地重复。问题正在减少，直到你只有一个组:最后一个，你知道你的新解决方案是否更好，如果有更好的，你可以用它抛弃另一个更糟的解决方案。
private static int estimate(int[] n, int m, int begin, int end) {
return (((n[end - 1] - n[begin]) / m) + 1 )/2;
}
private static int calculate(int[] n, int m, int begin, int end, int estimatedX){
if (m == 1){
return estimate(n, 1, begin, end);
} else {
int bestX = estimatedX;
for (int i = begin + 1; i <= end + 1 - m; i++) {
// It split the problem:
int firstGroupX = estimate(n, 1, begin, i);
if (firstGroupX < bestX){
bestX = Math.min(bestX, Math.max(firstGroupX, calculate(n, m-1, i, end, bestX)));
} else {
i = end;
}
}
return bestX;
}
}
public static void main(String[] args) {
int[] n = {1, 3, 8, 10, 18, 20, 25};
int m = 2;
Arrays.sort(n);
System.out.println(calculate(n, m, 0, n.length, estimate(n, m, 0, n.length)));
}编辑：
长数字版本:主要思想，它寻找“岛屿”的距离，并将问题分成不同的岛屿。就像分而治之一样，它把“m”分配到岛屿上。
private static long estimate(long[] n, long m, int begin, int end) {
return (((n[end - 1] - n[begin]) / m) + 1) / 2;
}
private static long calculate(long[] n, long m, int begin, int end, long estimatedX) {
if (m == 1) {
return estimate(n, 1, begin, end);
} else {
long bestX = estimatedX;
for (int i = begin + 1; i <= end + 1 - m; i++) {
long firstGroupX = estimate(n, 1, begin, i);
if (firstGroupX < bestX) {
bestX = Math.min(bestX, Math.max(firstGroupX, calculate(n, m - 1, i, end, bestX)));
} else {
i = end;
}
}
return bestX;
}
}
private static long solver(long[] n, long m, int begin, int end) {
long estimate = estimate(n, m, begin, end);
PriorityQueue<long[]> islands = new PriorityQueue<>((p0, p1) -> Long.compare(p1[0], p0[0]));
int islandBegin = begin;
for (int i = islandBegin; i < end -1; i++) {
if (n[i + 1] - n[i] > estimate) {
long estimatedIsland = estimate(n, 1, islandBegin, i+1);
islands.add(new long[]{estimatedIsland, islandBegin, i, 1});
islandBegin = i+1;
}
}
long estimatedIsland = estimate(n, 1, islandBegin, end);
islands.add(new long[]{estimatedIsland, islandBegin, end, 1});
long result;
if (islands.isEmpty() || m < islands.size()) {
result = calculate(n, m, begin, end, estimate);
} else {
long mFree = m - islands.size();
while (mFree > 0) {
long[] island = islands.poll();
island[3]++;
island[0] = solver(n, island[3], (int) island[1], (int) island[2]);
islands.add(island);
mFree--;
}
result = islands.poll()[0];
}
return result;
}
public static void main(String[] args) {
long[] n = new long[63];
for (int i = 1; i < n.length; i++) {
n[i] = 2*n[i-1]+1;
}
long m = 32;
Arrays.sort(n);
System.out.println(solver(n, m, 0, n.length));
}Stack Overflow用户
发布于 2016-01-16 09:49:20
提示
假设你有这个名单
1 3 8 10 18 20 25想找出如果x等于2，需要多少个组来覆盖这个集合。
您可以通过选择第一个整数为1+x (1是列表中最小的数字)，以贪婪的方式解决这个问题。这将覆盖到1+x+x=5的所有元素，然后简单地重复这个过程，直到覆盖所有的数字。
因此，在这种情况下，下一个未发现的数字是8，所以我们选择8+x=10并覆盖第二组中的10+x=12为止的所有数字。
同样，第三组将涵盖18 24名，第四组将涵盖25 29名。
这个x值需要4组。这太多了，所以我们需要增加x，然后再试一次。
您可以使用二分法来确定x的最小值，它涵盖了m组中的所有数字。
Stack Overflow用户
发布于 2016-01-16 08:02:01
一个有效的算法可以是(假设列表是排序的) ->
- 我们可以把列表看作是'm‘整数的组。
- 现在，对于每个组计算'last_element - first_element+1'，并将这个值的最大值存储在变量中，例如'ans‘。
- 现在'x‘的值是'ans/2’。
我希望这个算法的工作原理很清楚。
https://stackoverflow.com/questions/34824587
复制相似问题
腾讯云开发者
