Рубрики

Добавление элементов массива до тех пор, пока каждый элемент не станет больше или равен k

Нам дан список из N несортированных элементов, нам нужно найти минимальное количество шагов, в которые можно добавить элементы списка, чтобы все элементы были больше или равны K. Мы можем добавить два элемента вместе и сделать их одним.

Примеры:

Input : arr[] = {1 10 12 9 2 3}
          K = 6
Output : 2
First we add (1 + 2), now the new list becomes 
3 10 12 9 3, then we add (3 + 3),  now the new 
list becomes 6 10 12 9, Now all the elements in 
the list are greater than 6. Hence the output is 
2 i:e 2 operations are required 
to do this.

Как видно из приведенного выше объяснения, нам нужно извлечь два наименьших элемента и затем добавить их сумму в список. Нам нужно продолжать этот шаг, пока все элементы не будут больше или равны K.

Метод 1 (грубая сила):
Мы можем создать простой массив, отсортировать его, а затем добавить два минимальных элемента и продолжать хранить их обратно в массиве, пока все элементы не станут больше K.

Способ 2 (эффективный):
Если мы посмотрим поближе, то заметим, что эта проблема похожа на кодирование Хаффмана . Мы используем Min Heap в качестве основных операций здесь — извлечение min и вставка. Обе эти операции могут быть выполнены за O (Log n).

C ++

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

using namespace std;

  
// Класс для Min Heap

class MinHeap

{

    int *harr;

    int capacity; // максимальный размер

    int heap_size; // Текущий счет

public:

    // Конструктор

    MinHeap(int *arr, int capacity);

  

    // сложить поддерево с корнем в

    // данный индекс

    void heapify(int );

  

    int parent(int i)

    {

        return (i-1)/2;

    }

  

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

    // узел по индексу i

    int left(int i)

    {

        return (2*i + 1);

    }

  

    // чтобы получить индекс правого потомка

    // узел по индексу i

    int right(int i)

    {

        return (2*i + 2);

    }

  

    // чтобы извлечь корень, который является

    // минимальный элемент

    int extractMin();

  

    // Возвращает минимальный ключ (ключ при

    // root) из минимальной кучи

    int getMin()

    {

        return harr[0];

    }

  

    int getSize()

    {

        return heap_size;

    }

  

    // Вставляем новый ключ 'k'

    void insertKey(int k);

};

  
// Конструктор: строит кучу из
// заданный массив a [] заданного размера

MinHeap::MinHeap(int arr[], int n)

{

    heap_size = n;

    capacity = n;

    harr = new int[n];

  

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

        harr[i] = arr[i];

  

    // строим кучу из первого

    // неконечный узел путем вызова max

    // функция heapify

    for (int i=n/2-1; i>=0; i--)

        heapify(i);

}

  
// Вставляем новый ключ 'k'

void MinHeap::insertKey(int k)

{

    // Сначала вставляем новый ключ в конце

    heap_size++;

    int i = heap_size - 1;

    harr[i] = k;

  

    // Исправляем свойство min heap, если оно нарушено

    while (i != 0 && harr[parent(i)] > harr[i])

    {

        swap(harr[i], harr[parent(i)]);

        i = parent(i);

    }

}

  
// Метод для удаления минимального элемента
// (или root) из минимальной кучи

int MinHeap::extractMin()

{

    if (heap_size <= 0)

        return INT_MAX;

    if (heap_size == 1)

    {

        heap_size--;

        return harr[0];

    }

  

    // Сохраняем минимальное значение и

    // удаляем из кучи

    int root = harr[0];

    harr[0] = harr[heap_size-1];

    heap_size--;

    heapify(0);

  

    return root;

}

  
// Рекурсивный метод для подкачки поддерева
// с корнем по заданному индексу. Этот метод
// предполагает, что поддеревья уже
// куча

void MinHeap::heapify(int i)

{

    int l = left(i);

    int r = right(i);

    int smallest = i;

    if (l < heap_size && harr[l] < harr[i])

        smallest = l;

    if (r < heap_size && harr[r] < harr[smallest])

        smallest = r;

    if (smallest != i)

    {

        swap(harr[i], harr[smallest]);

        heapify(smallest);

    }

}

  
// Возвращает количество шагов, необходимых для
// все элементы больше или равны
// k добавлением элементов

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

{

    // Создаем минимальную кучу элементов массива

    MinHeap h(arr, n);

  

    long int res = 0;

  

    while (h.getMin() < k)

    {

        if (h.getSize() == 1)

            return -1;

  

        // Извлечь два минимальных элемента

        // и вставить их сумму

        int first = h.extractMin();

        int second = h.extractMin();

        h.insertKey(first + second);

  

        res++;

    }

  

    return res;

}

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

int main()

{

    int arr[] = {1, 10, 12, 9, 2, 3};

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

    int k = 6;

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

    return 0;

}

Джава

// Java-программа для подсчета минимальных шагов, чтобы сделать все
// элементы больше или равные k.

public class Add_Elements {

       

    // Класс для Min Heap

    static class MinHeap

    {

        int[] harr;

        int capacity; // максимальный размер

        int heap_size; // Текущий счет

      

        // Конструктор: строит кучу из

        // заданный массив a [] заданного размера

        MinHeap(int arr[], int n)

        {

            heap_size = n;

            capacity = n;

            harr = new int[n];

           

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

                harr[i] = arr[i];

           

            // строим кучу из первого

            // неконечный узел путем вызова max

            // функция heapify

            for (int i=n/2-1; i>=0; i--)

                heapify(i);

        }

       

        // Рекурсивный метод для подкачки поддерева

        // с корнем по заданному индексу. Этот метод

        // предполагает, что поддеревья уже

        // куча

        void heapify(int i)

        {

            int l = left(i);

            int r = right(i);

            int smallest = i;

            if (l < heap_size && harr[l] < harr[i])

                smallest = l;

            if (r < heap_size && harr[r] < harr[smallest])

                smallest = r;

            if (smallest != i)

            {

                int temp = harr[i];

                harr[i] = harr[smallest];

                harr[smallest] = temp;

                heapify(smallest);

            }

        }

       

        static int parent(int i)

        {

            return (i-1)/2;

        }

       

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

        // узел по индексу i

        static int left(int i)

        {

            return (2*i + 1);

        }

       

        // чтобы получить индекс правого потомка

        // узел по индексу i

        int right(int i)

        {

            return (2*i + 2);

        }

       

        // Метод для удаления минимального элемента

        // (или root) из минимальной кучи

        int extractMin()

        {

            if (heap_size <= 0)

                return Integer.MAX_VALUE;

            if (heap_size == 1)

            {

                heap_size--;

                return harr[0];

            }

           

            // Сохраняем минимальное значение и

            // удаляем из кучи

            int root = harr[0];

            harr[0] = harr[heap_size-1];

            heap_size--;

            heapify(0);

           

            return root;

        }

       

        // Возвращает минимальный ключ (ключ при

        // root) из минимальной кучи

        int getMin()

        {

            return harr[0];

        }

       

        int getSize()

        {

            return heap_size;

        }

       

        // Вставляем новый ключ 'k'

        void insertKey(int k)

        {

            // Сначала вставляем новый ключ в конце

            heap_size++;

            int i = heap_size - 1;

            harr[i] = k;

           

            // Исправляем свойство min heap, если оно нарушено

            while (i != 0 && harr[parent(i)] > harr[i])

            {

                 int temp = harr[i];

                 harr[i] = harr[parent(i)];

                 harr[parent(i)] = temp;

                 i = parent(i);

            }

        }

    }

       

       

    // Возвращает количество шагов, необходимых для

    // все элементы больше или равны

    // k добавлением элементов

    static int countMinOps(int arr[], int n, int k)

    {

        // Создаем минимальную кучу элементов массива

        MinHeap h = new MinHeap(arr, n);

       

        int res = 0;

       

        while (h.getMin() < k)

        {

            if (h.getSize() == 1)

                return -1;

       

            // Извлечь два минимальных элемента

            // и вставить их сумму

            int first = h.extractMin();

            int second = h.extractMin();

            h.insertKey(first + second);

       

            res++;

        }

       

        return res;

    }

       

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

    public static void main(String args[])

    {

        int arr[] = {1, 10, 12, 9, 2, 3};

        int n  = arr.length;

        int k = 6;

        System.out.println(countMinOps(arr, n, k));

    }

}
// Этот код предоставлен Sumit Ghosh

C #

// AC # программа для подсчета минимальных шагов, чтобы сделать все
// элементы больше или равные k.

using System;

      

public class Add_Elements 

{

      

    // Класс для Min Heap

    public class MinHeap

    {

        public int[] harr;

        public int capacity; // максимальный размер

        public int heap_size; // Текущий счет

      

        // Конструктор: строит кучу из

        // заданный массив a [] заданного размера

        public MinHeap(int []arr, int n)

        {

            heap_size = n;

            capacity = n;

            harr = new int[n];

          

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

                harr[i] = arr[i];

          

            // строим кучу из первого

            // неконечный узел путем вызова max

            // функция heapify

            for (int i = n/2-1; i >= 0; i--)

                heapify(i);

        }

      

        // Рекурсивный метод для подкачки поддерева

        // с корнем по заданному индексу. Этот метод

        // предполагает, что поддеревья уже

        // куча

        public void heapify(int i)

        {

            int l = left(i);

            int r = right(i);

            int smallest = i;

            if (l < heap_size && harr[l] < harr[i])

                smallest = l;

            if (r < heap_size && harr[r] < harr[smallest])

                smallest = r;

            if (smallest != i)

            {

                int temp = harr[i];

                harr[i] = harr[smallest];

                harr[smallest] = temp;

                heapify(smallest);

            }

        }

      

        public static int parent(int i)

        {

            return (i-1)/2;

        }

      

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

        // узел по индексу i

        static int left(int i)

        {

            return (2*i + 1);

        }

      

        // чтобы получить индекс правого потомка

        // узел по индексу i

        public int right(int i)

        {

            return (2*i + 2);

        }

      

        // Метод для удаления минимального элемента

        // (или root) из минимальной кучи

        public int extractMin()

        {

            if (heap_size <= 0)

                return int.MaxValue;

            if (heap_size == 1)

            {

                heap_size--;

                return harr[0];

            }

          

            // Сохраняем минимальное значение и

            // удаляем из кучи

            int root = harr[0];

            harr[0] = harr[heap_size-1];

            heap_size--;

            heapify(0);

          

            return root;

        }

      

        // Возвращает минимальный ключ (ключ при

        // root) из минимальной кучи

        public int getMin()

        {

            return harr[0];

        }

      

        public int getSize()

        {

            return heap_size;

        }

      

        // Вставляем новый ключ 'k'

        public void insertKey(int k)

        {

            // Сначала вставляем новый ключ в конце

            heap_size++;

            int i = heap_size - 1;

            harr[i] = k;

          

            // Исправляем свойство min heap, если оно нарушено

            while (i != 0 && harr[parent(i)] > harr[i])

            {

                int temp = harr[i];

                harr[i] = harr[parent(i)];

                harr[parent(i)] = temp;

                i = parent(i);

            }

        }

    }

      

      

    // Возвращает количество шагов, необходимых для

    // все элементы больше или равны

    // k добавлением элементов

    static int countMinOps(int []arr, int n, int k)

    {

        // Создаем минимальную кучу элементов массива

        MinHeap h = new MinHeap(arr, n);

      

        int res = 0;

      

        while (h.getMin() < k)

        {

            if (h.getSize() == 1)

                return -1;

      

            // Извлечь два минимальных элемента

            // и вставить их сумму

            int first = h.extractMin();

            int second = h.extractMin();

            h.insertKey(first + second);

      

            res++;

        }

      

        return res;

    }

      

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

    public static void Main(String []args)

    {

        int []arr = {1, 10, 12, 9, 2, 3};

        int n = arr.Length;

        int k = 6;

        Console.WriteLine(countMinOps(arr, n, k));

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

2

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

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

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

Добавление элементов массива до тех пор, пока каждый элемент не станет больше или равен k

0.00 (0%) 0 votes