Рубрики

Проблема распространения шоколада

Дан массив из n целых чисел, где каждое значение представляет количество конфет в пакете. Каждый пакет может иметь различное количество конфет. Есть м студентов, задача состоит в том, чтобы распределить шоколадные пакеты так, чтобы:

  1. Каждый студент получает один пакет.
  2. Разница между количеством конфет в пакете с максимальным количеством конфет и пакетом с минимальным количеством конфет, предоставленных студентам, минимальна.

Примеры:

Input : arr[] = {7, 3, 2, 4, 9, 12, 56}
m = 3
Output: Minimum Difference is 2
We have seven packets of chocolates and
we need to pick three packets for 3 students
If we pick 2, 3 and 4, we get the minimum
difference between maximum and minimum packet
sizes.

Input : arr[] = {3, 4, 1, 9, 56, 7, 9, 12}
m = 5
Output: Minimum Difference is 6
The set goes like 3,4,7,9,9 and the output
is 9-3 = 6

Input : arr[] = {12, 4, 7, 9, 2, 23, 25, 41,
30, 40, 28, 42, 30, 44, 48,
43, 50}
m = 7
Output: Minimum Difference is 10
We need to pick 7 packets. We pick 40, 41,
42, 44, 48, 43 and 50 to minimize difference
between maximum and minimum.

Источник: Flipkart Интервью Опыт

Простое решение состоит в том, чтобы сгенерировать все подмножества размера m arr [0..n-1]. Для каждого подмножества найдите разницу между максимальным и минимальным элементами в нем. Наконец, верните минимальную разницу.

Эффективное решение основано на наблюдении, что для минимизации разницы мы должны выбирать последовательные элементы из отсортированного пакета. Сначала мы сортируем массив arr [0..n-1], затем находим подмассив размером m с минимальной разницей между последним и первым элементами.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

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

using namespace std;

  
// arr [0..n-1] представляет размеры пакетов
// m - количество студентов.
// Возвращает минимальную разницу между максимумом
// и минимальные значения распределения.

int findMinDiff(int arr[], int n, int m)

{

    // если нет конфет или номера

    // студентов 0

    if (m==0 || n==0)

        return 0;

  

    // Сортировка данных пакетов

    sort(arr, arr+n);

  

    // Количество студентов не может быть больше

    // количество пакетов

    if (n < m)

       return -1;

  

    // Наибольшее количество конфет

    int min_diff = INT_MAX;

  

    // Находим подмассив размером m такой, что

    // разница между последним (максимальная в случае

    // отсортировано) и первое (минимум в случае

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

    int first = 0, last = 0;

    for (int i=0; i+m-1<n; i++)

    {

        int diff = arr[i+m-1] - arr[i];

        if (diff < min_diff)

        {

            min_diff = diff;

            first = i;

            last = i + m - 1;

        }

    }

    return (arr[last] - arr[first]);

}

  

int main()

{

    int arr[] = {12, 4, 7, 9, 2, 23, 25, 41,

                 30, 40, 28, 42, 30, 44, 48,

                 43, 50};

    int m = 7;  // Количество студентов

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

    cout << "Minimum difference is "

         << findMinDiff(arr, n, m);

    return 0;

}

Джава

// JAVA-код для распространения шоколада
// Проблема

import java.util.*;

  

class GFG {

      

    // arr [0..n-1] представляет размеры

    // пакеты. м количество студентов.

    // Возвращает минимальную разницу между

    // максимальные и минимальные значения

    // распространение.

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

                                    int m)

    {

        // если нет конфет или

        // количество студентов 0

        if (m == 0 || n == 0)

            return 0;

       

        // Сортировка данных пакетов

        Arrays.sort(arr);

       

        // Количество студентов не может быть

        // больше количества пакетов

        if (n < m)

           return -1;

       

        // Наибольшее количество конфет

        int min_diff = Integer.MAX_VALUE;

       

        // Находим подмассив размером m

        // такая, что разница между

        // последний (максимум в случае

        // отсортировано) и первое (минимум в

        // случай отсортированных) элементов

        // подрешетка минимальная.

        int first = 0, last = 0;

        for (int i = 0; i + m - 1 < n; i++)

        {

            int diff = arr[i+m-1] - arr[i];

            if (diff < min_diff)

            {

                min_diff = diff;

                first = i;

                last = i + m - 1;

            }

        }

        return (arr[last] - arr[first]);

    }

      

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args) 

    {

        int arr[] = {12, 4, 7, 9, 2, 23,

                    25, 41, 30, 40, 28,

                    42, 30, 44, 48, 43,

                   50};

                     

        int m = 7// Количество студентов

          

        int n = arr.length;

        System.out.println("Minimum difference is "

                + findMinDiff(arr, n, m));

              

    }

}
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# Python3 программа для решения
# шоколадная раздача
# проблема

  

import sys;

  
# arr [0..n-1] представляет размеры пакетов
# m - количество студентов.
# Возвращает минимальную разницу между максимумом
# и минимальные значения распределения.

def findMinDiff(arr, n, m):

  

    # если нет конфет или номера

    количество студентов 0

    if (m==0 or n==0):

        return 0

  

    # Сортировка данных пакетов

    arr.sort()

  

    # Количество студентов не может быть больше

    # количество пакетов

    if (n < m):

        return -1

  

    # Наибольшее количество конфет

    min_diff = sys.maxsize

  

    # Найти подмассив размером m такой, что

    # разница между последним (максимальная в случае

    № отсортировано) и первое (минимум в случае

    # отсортировано) элементов подмассива минимально.

    first = 0

    last = 0

    i=0

    while(i+m-1<n ):

      

        diff = arr[i+m-1] - arr[i]

        if (diff < min_diff):

          

            min_diff = diff

            first = i

            last = i + m - 1

          

        i+=1

          

    return (arr[last] - arr[first])

  
Код водителя

if __name__ == "__main__":

    arr = [12, 4, 7, 9, 2, 23, 25, 41,

          30, 40, 28, 42, 30, 44, 48

          43, 50]

    m = 7 Количество студентов

    n = len(arr)

    print("Minimum difference is", findMinDiff(arr, n, m))

      
# Этот код предоставлен Смитой

C #

// C # код для распространения шоколада
// Проблема

using System;

  

class GFG {

      

    // arr [0..n-1] представляет размеры

    // пакеты. м количество студентов.

    // Возвращает минимальную разницу между

    // максимальные и минимальные значения

    // распространение.

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

                                    int m)

    {

          

        // если нет конфет или

        // количество студентов 0

        if (m == 0 || n == 0)

            return 0;

      

        // Сортировка данных пакетов

        Array.Sort(arr);

      

        // Количество студентов не может быть

        // больше количества пакетов

        if (n < m)

            return -1;

      

        // Наибольшее количество конфет

        int min_diff = int.MaxValue;

      

        // Находим подмассив размером m

        // такая, что разница между

        // последний (максимум в случае

        // отсортировано) и первое (минимум в

        // случай отсортированных) элементов

        // подрешетка минимальная.

        int first = 0, last = 0;

        for (int i = 0; i + m - 1 < n; i++)

        {

            int diff = arr[i+m-1] - arr[i];

              

            if (diff < min_diff)

            {

                min_diff = diff;

                first = i;

                last = i + m - 1;

            }

        }

          

        return (arr[last] - arr[first]);

    }

      

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main() 

    {

        int []arr = {12, 4, 7, 9, 2, 23,

                    25, 41, 30, 40, 28,

                    42, 30, 44, 48, 43,

                                    50};

                      

        int m = 7; // Количество студентов

          

        int n = arr.Length;

          

        Console.WriteLine("Minimum difference is "

                    + findMinDiff(arr, n, m));

              

    }

}

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

PHP

<?php
// PHP программа для решения
// шоколадная раздача
// проблема

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

function findMinDiff($arr, $n, $m)

{

    // если нет

    // шоколад или номер

    // студентов 0

    if ($m == 0 || $n == 0)

        return 0;

  

    // Сортировка данных пакетов

    sort($arr);

  

    // Количество студентов

    // не может быть больше чем

    // количество пакетов

    if ($n < $m)

    return -1;

  

    // Наибольшее число

    // конфет

    $min_diff = PHP_INT_MAX;

  

    // Находим подмассив размера

    // м такая разница

    // между последним (максимум в

    // случай отсортирован) и первый

    // (минимум в случае сортировки)

    // элементы подмассива минимальны.

    $first = 0; $last = 0;

    for ($i = 0; 

         $i + $m - 1 < $n; $i++)

    {

        $diff = $arr[$i + $m - 1] -

                $arr[$i];

        if ($diff < $min_diff)

        {

            $min_diff = $diff;

            $first = $i;

            $last = $i + $m - 1;

        }

    }

    return ($arr[$last] - 

            $arr[$first]);

}

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

$arr = array(12, 4, 7, 9, 2, 23, 

             25, 41, 30, 40, 28, 

             42, 30, 44, 48, 43, 50);

               

$m = 7; // Количество студентов

$n = sizeof($arr);

echo "Minimum difference is ",

    findMinDiff($arr, $n, $m);

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


Выход:

Minimum difference is 10

Сложность времени: O (n Log n), так как мы применяем сортировку перед поиском в подмассиве.

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

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

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

Проблема распространения шоколада

0.00 (0%) 0 votes