Проверьте, могут ли элементы массива быть максимизированы до M, добавив все элементы из другого массива

Опубликовано: 1 Января, 2022

Учитывая положительное целое число M и два массива arr [] и value [] из N и K положительных целых чисел соответственно, задача состоит в том, чтобы добавить каждый элемент в value [] к элементу в arr [] таким образом, чтобы после выполнения всех сложений, максимальный элемент в массиве не больше M. Если это возможно, то выведите «Да» . В противном случае выведите «Нет» .
Примеры:

Input: arr[] = {5, 9, 3, 8, 7}, value[] = {1, 2, 3, 4}, M = 9
Output: Yes
Explanation:
Add 1 & 3 to arr[0] maximizing it to 9.
Add 2 & 4 to arr[2] maximizes it to 9.
Hence, the final arr becomes {9, 9, 9, 8, 7}.
Input: arr[] = {5, 8, 3, 8, 7}, value[] = {1, 2, 3, 4}, M = 8
Output: No
Explanation:
Adding 1 to arr[4], 3 to arr[0] and 4 to arr[2], the array is modified to {8, 8, 7, 8, 8}.
The current maximum element in arr[] is 8.
Hence, only 2 needs to be added from value[] to any element of arr[].
But, on adding 2 to any element in arr[], the maximum element in the array exceeds 8.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:
Самый простой подход - выбрать любые K элементов из данного массива arr [] и добавить K значений в массив value [] с этими выбранными K значениями. Эти K значений могут быть добавлены к выбранным K числам массива arr [] в K! способами (в худшем случае).
Сложность времени: O ( ^N P _K )
Эффективный подход:
Выполните следующие действия, чтобы решить проблему:

Отсортируйте элементы в массиве value [] в порядке убывания.
Сохраните все элементы arr [] в очереди с минимальным приоритетом.
Теперь извлеките минимальный элемент (скажем, X ) из очереди приоритетов и добавьте элементы из массива value [] в X.
При добавлении значения из массива value [] к X превышает M , затем вставьте элемент X в очередь приоритетов и повторите вышеуказанный шаг для следующего минимального значения в очереди приоритетов.
Если все элементы в значении [] добавляются к некоторым элементам в arr [], тогда «Да» , иначе выведите «Нет» .

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

C ++

 // C++ Program to implement the
 // above approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function which checks if all
 // additions are possible
 void solve( int ar[], int values[],
        int N, int K, int M)
 {
    // Sorting values[] in
    // decreasing order
    sort(values, values + K,
        greater< int >()); 
    // Minimum priority queue which
    // contains all the elements
    // of array arr[]
    priority_queue< int , vector< int >,
                greater< int > >
        pq;
    for ( int x = 0; x < N; x++) {
        pq.push(ar[x]);
    }
    // poss stores whether all the
    // additions are possible
    bool poss = true ;
    for ( int x = 0; x < K; x++) { 
        // Minium value in the
        // priority queue
        int mini = pq.top();
        pq.pop();
        int val = mini + values[x]; 
        // If on addition it exceeds
        // M then not possible
        if (val > M) {
            poss = false ;
            break ;
        }
        pq.push(val);
    }
    // If all elements are added
    if (poss) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
 }
 // Driver Code
 int main()
 {
    int ar[] = { 5, 9, 3, 8, 7 };
    int N = 5; 
    int values[] = { 1, 2, 3, 4 };
    int K = 4; 
    int M = 9; 
    solve(ar, values, N, K, M);
    return 0;
 }

Джава

 // Java program to implement the
 // above approach
 import java.io.*;
 import java.util.*;
 class GFG{
           
// Function which checks if all
 // additions are possible
 static void solve(Integer ar[], Integer values[],
                  int N, int K, int M)
 {
    
    // Sorting values[] in
    // decreasing order
    Arrays.sort(values, (a, b) -> b - a);
    // Minimum priority queue which
    // contains all the elements
    // of array arr[]
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    
    for ( int x = 0 ; x < N; x++)
    {
        pq.add(ar[x]);
    }
    
    // poss stores whether all the
    // additions are possible
    boolean poss = true ;
    for ( int x = 0 ; x < K; x++)
    {
        
        // Minium value in the
        // priority queue
        int mini = pq.peek();
        pq.poll();
        
        int val = mini + values[x];
        
        // If on addition it exceeds
        // M then not possible
        if (val > M)
        {
            poss = false ;
            break ;
        }
        pq.add(val);
    }
    
    // If all elements are added
    if (poss)
    {
        System.out.println( "Yes" );
    }
    else
    {
        System.out.println( "No" );
    }
 }
 // Driver Code
 public static void main(String args[])
 {
    Integer ar[] = { 5 , 9 , 3 , 8 , 7 };
    int N = 5 ;
    
    Integer values[] = { 1 , 2 , 3 , 4 };
    int K = 4 ;
    
    int M = 9 ;
    
    solve(ar, values, N, K, M);
 }
 }
 // This code is contributed by offbeat

Python3

 # Python3 program to implement the
 # above approach
 from queue import PriorityQueue
 # Function which checks if all
 # additions are possible
 def solve(ar, values, N, K, M):
     
    # Sorting values[] in
    # decreasing order
    values.sort(reverse = True )
     
    # Minimum priority queue which
    # contains all the elements
    # of array arr[]
    pq = PriorityQueue()
    
    for x in range (N):
    
        pq.put(ar[x]);
      
    # poss stores whether all the
    # additions are possible
    poss = True ;
    
    for x in range (K):
         
        # Minium value in the
        # priority queue
        mini = pq.get();
         
        val = mini + values[x];
         
        # If on addition it exceeds
        # M then not possible
        if (val > M):
          poss = False ;
          break ;
        
        pq.put(val);
    
    # If all elements are added
    if (poss):
        print ( "Yes" );
    else :
        print ( "No" );
 # Driver Code
 if __name__ = = '__main__' : 
    ar = [ 5 , 9 , 3 , 8 , 7 ]
    N = 5 ;
     
    values = [ 1 , 2 , 3 , 4 ]
    
    K = 4 ;
     
    M = 9 ;
     
    solve(ar, values, N, K, M);
 # This code is contributed by rutvik_56

C #

 // C# Program to implement the
 // above approach
 using System;
 using System.Collections.Generic;
 class GFG
 {
    
    // Function which checks if all
    // additions are possible
    static void solve( int [] ar, int [] values,
            int N, int K, int M)
    {
     
        // Sorting values[] in
        // decreasing order
        Array.Sort(values);
        Array.Reverse(values);
     
        // Minimum priority queue which
        // contains all the elements
        // of array arr[]
        List< int > pq = new List< int >();
     
        for ( int x = 0; x < N; x++)
        {
            pq.Add(ar[x]);
        }
        
        pq.Sort();
     
        // poss stores whether all the
        // additions are possible
        bool poss = true ;
        for ( int x = 0; x < K; x++)
        {
     
            // Minium value in the
            // priority queue
            int mini = pq[0];
            pq.RemoveAt(0);
            int val = mini + values[x];
     
            // If on addition it exceeds
            // M then not possible
            if (val > M)
            {
                poss = false ;
                break ;
            }
            pq.Add(val);
            pq.Sort();
        }
     
        // If all elements are added
        if (poss)
        {
            Console.WriteLine( "Yes" );
        }
        else
        {
            Console.WriteLine( "No" );
        }
    }
  // Driver code
  static void Main()
  {
    int [] ar = { 5, 9, 3, 8, 7 };
    int N = 5;
 
    int [] values = { 1, 2, 3, 4 };
    int K = 4;
 
    int M = 9;
 
    solve(ar, values, N, K, M);
  }
 }
 // This code is contributed by divyeshrabadiya07.

Выход:

Yes

Олимпиады по программированию Алгоритмы Структуры данных

Проверьте, могут ли элементы массива быть максимизированы до M, добавив все элементы из другого массива

C ++

Джава

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ