6

昨日、インタビューに出演しました。私は質問の1つで立ち往生していました。ここでも同じことを尋ねています。

x 軸上の点を示す配列が与えられ、N 個の点があります。Mコインもプレゼント。

Remember N >= M

任意の 2 点間の最小距離を最大化する必要があります。

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

準備の整ったアルゴリズムを使用できます。順序付けられたシリーズの最初と最後の点を選択します (これが可能な最大距離であるため)。次に、より大きなパーティションを選択するよりも、それらの平均に最も近いポイントを選択します（他の回答では片側の距離が短くなるため）。その後、必要な回数だけ繰り返します。

于 2012-09-08T07:17:47.840 に答える
-1

動的計画法を使用する必要があります。なぜなら、最適な答えが必要だからです。あなたの問題は、「コインの変更」の問題に似ています。問題のように、コインがなく、最小距離を見つけたいとします(最小コイン数の代わりに)。

次のリンクを読むことができます: Change Coin problem & Dynamic Programming

于 2012-09-08T07:30:18.380 に答える