6

昨天，我出现在一个采访中。我被困在一个问题中，我在这里问同样的问题。

给定一个数组，显示 x 轴上的点，有 N 个点。还赠送了M币。

Remember N >= M

您必须最大化任意两点之间的最小距离。

Example: Array : 1 3 6 12
         3 coins are given.
         If you put coins on 1, 3, 6 points Then distance between coins are : 2, 3 
         So it gives 2 as answer 
         But we can improve further
         If we put coins at 1, 6, 12 points.
         Then distances are 5, 6
         So correct answer is : 5

请帮助我，因为我完全陷入了这个问题。

4

3 回答 3

1

这是我的O(N 2 )方法。首先，生成所有可能的距离；

int dist[1000000][3], ndist = 0;
for(int i = 0; i < n; i ++) {
    for(int j = i + 1; j < n; j ++) {
        dist[ndist][0] = abs(points[i] - points[j]);
        dist[ndist][1] = i; //save the first point
        dist[ndist][2] = j; //save the second point
    }
}

现在按降序对距离进行排序：

sort(dist, dist + ndist, cmp);

在哪里cmp：

bool cmp(int x[], int y[]) {
    return (x[0] > y[0]);
}

扫描数组，只要您没有m选择点，就添加点：

int chosen = 0;
int ans;
for(int i = 0; i < ndist; i ++) {
    int whatadd = (!visited[dist[i][1]]) + (!visited[dist[i][2]); //how many new points we'll get if we take this one
    if(chosen + whatadd > m) {
        break;
    }
    visited[dist[i][1]] = 1;
    visited[dist[i][2]] = 1;
    chosen += whatadd;
    ans = dist[i][0]; //ans is the last dist[i][0] chosen, since they're sorted in decreasing order
}
if(chosen != m) {
    //you need at most one extra point, choose the optimal available one
    //left as an exercise :)
}

我希望这有帮助！

于 2012-09-08T08:07:31.483 回答
0

您可以使用 greyy 算法：您选择有序系列的第一个和最后一个点（因为这是可能的最大距离）。然后你选择最接近它们平均值的点（因为任何其他答案都会在一侧给出更小的距离），而不是选择更大的分区。然后根据需要重复多次。

于 2012-09-08T07:17:47.840 回答
-1

您必须使用动态编程。因为，您需要一个最佳答案。您的问题类似于“硬币的变化”问题。像这个问题一样，你没有硬币，你想找到最小距离。（而不是最小的硬币）。

您可以阅读以下链接：Change Coin problem & Dynamic Programming

于 2012-09-08T07:30:18.380 回答