Рубрики

Разместите k элементов так, чтобы минимальное расстояние было максимальным

Дан массив, представляющий n позиций по прямой. Найти k (где k <= n) элементов из массива так, чтобы максимальное расстояние между любыми двумя (последовательными точками среди k точек) было максимальным.

Примеры :

Input : arr[] = {1, 2, 8, 4, 9}
            k = 3
Output : 3
Largest minimum distance = 3
3 elements arranged at positions 1, 4 and 8, 
Resulting in a minimum distance of 3

Input  : arr[] = {1, 2, 7, 5, 11, 12}
             k = 3
Output : 5
Largest minimum distance = 5
3 elements arranged at positions 1, 7 and 12, 
resulting in a minimum distance of 5 (between
7 and 12)

Наивное решение состоит в том, чтобы рассмотреть все подмножества размера 3 и найти минимальное расстояние для каждого подмножества. Наконец верните наибольшее из всех минимальных расстояний.

Эффективное решение основано на бинарном поиске . Сначала мы отсортируем массив. Теперь мы знаем, что максимально возможным значением результата является arr [n-1] — arr [0] (для k = 2). Мы делаем бинарный поиск для максимального результата для данного k. Начнем с середины максимально возможного результата. Если среднее является возможным решением, мы ищем правую половину середины. Иначе мы ищем левую половину. Чтобы проверить выполнимость, мы помещаем k элементов под данное среднее расстояние.

C ++

// C ++ программа для поиска наибольшего минимального расстояния
// среди k точек.
#include <bits/stdc++.h>

  

using namespace std;

  
// Возвращает true, если возможно организовать
// k элементов arr [0..n-1] с минимальным расстоянием
// указано как середина

bool isFeasible(int mid, int arr[], int n, int k)

{

    // Поместить первый элемент в позицию arr [0]

    int pos = arr[0];

  

    // Инициализируем количество размещенных элементов.

    int elements = 1;

  

    // Попробуйте разместить k элементов с минимумом

    // расстояние в середине.

    for (int i=1; i<n; i++)

    {

        if (arr[i] - pos >= mid)

        {

            // Поместить следующий элемент, если его

            // расстояние от ранее

            // размещенный элемент больше

            // чем текущая середина

            pos = arr[i];

            elements++;

  

            // Возвращаем, если все элементы размещены

            // успешно

            if (elements == k)

              return true;

        }

    }

    return 0;

}

  
// Возвращает наибольшее минимальное расстояние для k элементов
// в обр [0..n-1]. Если элементы не могут быть размещены,
// возвращает -1.

int largestMinDist(int arr[], int n, int k)

{

    // Сортировка позиций

    sort(arr,arr+n);

  

    // Инициализировать результат.

    int res = -1;

  

    // Рассмотрим максимально возможное расстояние

    int left = arr[0], right = arr[n-1];

  

    // Делаем бинарный поиск по наибольшему минимальному расстоянию

    while (left < right)

    {

        int mid = (left + right)/2;

  

        // Если возможно разместить k элементов

        // с минимальным расстоянием посередине, поиск

        // большее расстояние.

        if (isFeasible(mid, arr, n, k))

        {

            // Изменить значение переменной max на mid iff

            // все элементы могут быть успешно размещены

            res = max(res, mid);

            left = mid + 1;

        }

  

        // Если невозможно разместить k элементов, ищите

        // для меньшего расстояния

        else

            right = mid;

    }

  

    return res;

}

  
// Код драйвера

int main()

{

    int arr[] = {1, 2, 8, 4, 9};

    int n = sizeof(arr)/sizeof(arr[0]);

    int k = 3;

    cout << largestMinDist(arr, n, k);

    return 0;

}

Джава

// Java-программа для поиска крупнейших
// минимальное расстояние среди k точек.

import java.util.Arrays;

  

class GFG 

{
// Возвращает true, если это возможно
// упорядочить k элементов arr [0..n-1]
// с минимальным расстоянием в середине.

static boolean isFeasible(int mid, int arr[], 

                                int n, int k)

{

    // Поместить первый элемент в позицию arr [0]

    int pos = arr[0];

  

    // Инициализируем количество размещенных элементов.

    int elements = 1;

  

    // Попробуйте разместить k элементов с минимумом

    // расстояние в середине.

    for (int i=1; i<n; i++)

    {

        if (arr[i] - pos >= mid)

        {

            // Поместить следующий элемент, если его

            // расстояние от ранее

            // размещенный элемент больше

            // чем текущая середина

            pos = arr[i];

            elements++;

  

            // Возвращаем, если все элементы

            // успешно размещен

            if (elements == k)

            return true;

        }

    }

    return false;

}

  
// Возвращает наибольшее минимальное расстояние для
// k элементов в arr [0..n-1]. Если элементы
// не может быть размещен, возвращает -1.

static int largestMinDist(int arr[], int n, 

                                     int k)

{

    // Сортировка позиций

    Arrays.sort(arr);

  

    // Инициализировать результат.

    int res = -1;

  

    // Рассмотрим максимально возможное расстояние

    int left = arr[0], right = arr[n-1];

  

    // Делаем бинарный поиск по величине

    // минимальное расстояние

    while (left < right)

    {

        int mid = (left + right)/2;

  

        // Если возможно разместить k

        // элементы с минимальным расстоянием посередине,

        // поиск большего расстояния.

        if (isFeasible(mid, arr, n, k))

        {

            // Изменить значение переменной max на

            // середина, если все элементы могут быть

            // успешно размещен

            res = Math.max(res, mid);

            left = mid + 1;

        }

  

        // Если невозможно разместить k элементов,

        // ищем меньшее расстояние

        else

            right = mid;

    }

  

    return res;

}

  
// код драйвера

public static void main (String[] args)

{

    int arr[] = {1, 2, 8, 4, 9};

    int n = arr.length;

    int k = 3;

    System.out.print(largestMinDist(arr, n, k));

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Программа Python 3, чтобы найти самый большой минимум
# расстояние между k точками.

  
# Возвращает true, если это возможно
# k элементов arr [0..n-1] с минимальным
# расстояние указано в середине.

def isFeasible(mid, arr, n, k):

      

    # Поместить первый элемент в позицию arr [0]

    pos = arr[0]

  

    # Инициализировать количество размещенных элементов.

    elements = 1

  

    # Попробуйте разместить k элементов с минимумом

    # расстояние в середине.

    for i in range(1, n, 1):

        if (arr[i] - pos >= mid):

              

            # Поместить следующий элемент, если его расстояние

            # из ранее размещенного элемента

            # больше текущей середины

            pos = arr[i]

            elements += 1

  

            # Возврат, если все элементы размещены

            # успешно

            if (elements == k):

                return True

    return 0

  
# Возвращает наибольшее минимальное расстояние для k элементов
# в обр [0..n-1]. Если элементы не могут быть размещены,
# возвращает -1.

def largestMinDist(arr, n, k):

      

    # Сортировка позиций

    arr.sort(reverse = False)

  

    # Инициализировать результат.

    res = -1

  

    # Рассмотрим максимально возможное расстояние

    left = arr[0]

    right = arr[n - 1]

  

    # Делаем бинарный поиск по величине

    # минимальное расстояние

    while (left < right):

        mid = (left + right) / 2

  

        # Если можно разместить k элементов

        # с минимальным расстоянием в середине, поиск

        # большее расстояние.

        if (isFeasible(mid, arr, n, k)):

              

            # Изменить значение переменной max на mid iff

            # все элементы могут быть успешно размещены

            res = max(res, mid)

            left = mid + 1

  

        # Если невозможно разместить k элементов,

        # поиск меньшего расстояния

        else:

            right = mid

  

    return res

  
# Код драйвера

if __name__ == '__main__':

    arr = [1, 2, 8, 4, 9]

    n = len(arr)

    k = 3

    print(largestMinDist(arr, n, k))

  
# Этот код предоставлен
# Sanjit_prasad

C #

// C # программа для поиска крупнейших
// минимальное расстояние среди k точек.

using System;

  

public class GFG {

      

    // Возвращает true, если это возможно

    // упорядочить k элементов arr [0..n-1]

    // с минимальным расстоянием в середине.

    static bool isFeasible(int mid, int []arr, 

                                 int n, int k)

    {

          

        // Поместить первый элемент в arr [0]

        // позиция

        int pos = arr[0];

      

        // Инициализируем количество размещенных элементов.

        int elements = 1;

      

        // Попробуйте разместить k элементов с минимумом

        // расстояние в середине.

        for (int i = 1; i < n; i++)

        {

            if (arr[i] - pos >= mid)

            {

                  

                // Поместить следующий элемент, если его

                // расстояние от ранее

                // размещенный элемент больше

                // чем текущая середина

                pos = arr[i];

                elements++;

      

                // Возвращаем, если все элементы

                // успешно размещен

                if (elements == k)

                    return true;

            }

        }

          

        return false;

    }

      

    // Возвращает наибольшее минимальное расстояние для

    // k элементов в arr [0..n-1]. Если элементы

    // не может быть размещен, возвращает -1.

    static int largestMinDist(int []arr, int n, 

                                          int k)

    {

          

        // Сортировка позиций

        Array.Sort(arr);

      

        // Инициализировать результат.

        int res = -1;

      

        // Рассмотрим максимально возможный

        // расстояние

        int left = arr[0], right = arr[n-1];

      

        // Делаем бинарный поиск по величине

        // минимальное расстояние

        while (left < right)

        {

            int mid = (left + right) / 2;

      

            // Если возможно разместить k

            // элементы с минимальным расстоянием

            // середина, ищите большее расстояние.

            if (isFeasible(mid, arr, n, k))

            {

                // Изменить значение переменной

                // максимум до середины, если все элементы

                // может быть успешно размещен

                res = Math.Max(res, mid);

                left = mid + 1;

            }

      

            // Если невозможно разместить k

            // элементы, поиск ниже

            // расстояние

            else

                right = mid;

        }

      

        return res;

    }

      

    // код драйвера

    public static void Main ()

    {

        int []arr = {1, 2, 8, 4, 9};

        int n = arr.Length;

        int k = 3;

          

        Console.WriteLine(

            largestMinDist(arr, n, k));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для поиска крупнейших
// минимальное расстояние среди k точек.

  
// Возвращает true, если это возможно
// расположить k элементов
// arr [0..n-1] с минимальным
// расстояние указано как середина

function isFeasible($mid, $arr

                    $n, $k)

{

    // Поместить первый элемент

    // в позиции arr [0]

    $pos = $arr[0];

  

    // Инициализировать количество

    // элементы размещены.

    $elements = 1;

  

    // Попробуйте разместить k элементов

    // с минимальным расстоянием в середине.

    for ($i = 1; $i < $n; $i++)

    {

        if ($arr[$i] - $pos >= $mid)

        {

            // Поместить следующий элемент, если

            // его расстояние от

            // ранее размещенный

            // элемент больше

            // чем текущая середина

            $pos = $arr[$i];

            $elements++;

  

            // Возвращаем, если все элементы

            // успешно размещены

            if ($elements == $k)

            return true;

        }

    }

    return 0;

}

  
// Возвращает самый большой минимум
// расстояние для k элементов
// в обр [0..n-1]. Если элементы
// не может быть размещен, возвращает -1.

function largestMinDist($arr, $n, $k)

{

    // Сортировка позиций

    sort($arr);

  

    // Инициализировать результат.

    $res = -1;

  

    // Рассмотрим максимум

    // возможное расстояние

    $left = $arr[0];

    $right = $arr[$n - 1];

  

    // Делаем бинарный поиск

    // наибольшее минимальное расстояние

    while ($left < $right)

    {

        $mid = ($left + $right) / 2;

  

        // Если возможно разместить

        // k элементов с минимумом

        // расстояние в середине, поиск

        // большее расстояние.

        if (isFeasible($mid, $arr

                       $n, $k))

        {

            // Изменить значение переменной

            // максимально до середины, если все элементы

            // может быть успешно размещен

            $res = max($res, $mid);

            $left = $mid + 1;

        }

  

        // Если невозможно разместить

        // k элементов, поиск

        // меньшее расстояние

        else

            $right = $mid;

    }

  

    return $res;

}

  
// Код драйвера

$arr = array(1, 2, 8, 4, 9);

$n = sizeof($arr);

$k = 3;

echo largestMinDist($arr, $n, $k);

  
// Этот код предоставлен aj_36
?>


Выход :

3

Эта статья предоставлена Рагхавом Джаджодиа . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Разместите k элементов так, чтобы минимальное расстояние было максимальным

0.00 (0%) 0 votes