Número mínimo de días laborables necesarios para alcanzar cada uno de los puntajes dados

Dada una array arr[] que consta de N enteros y una array P[] que consta de M enteros tal que P[i] representa la puntuación obtenida al trabajar en el i- ésimo día . La tarea es encontrar la cantidad mínima de días necesarios para trabajar para lograr una puntuación de al menos arr[i] , para cada elemento de la array arr[i] .

Ejemplos:

Entrada: arr[] = {400, 200, 700}, P[] = {100, 300, 400, 500, 600}
Salida: 2 2 3 4 5
Explicación:
Los siguientes son el número de días necesarios para cada elemento de la array:

  1. arr[0](= 400): Para ganar 400 puntos, uno tiene que trabajar durante los primeros 2 días haciendo que el total de puntos sea igual a 100 + 300 = 400(>= arr[0]).
  2. arr[1](= 200): Para ganar 200 puntos uno tiene que trabajar durante los primeros 2 días haciendo un total de puntos = 100 + 300 = 400(>= arr[1]).
  3. arr[2](= 700): Para ganar 700 puntos uno tiene que trabajar durante los primeros 3 días haciendo un total de puntos = 100 + 300 + 400 = 800(>= arr[2]).

Entrada: arr[] = {1400}, P[] = {100, 300}
Salida: -1

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array arr[] y, para cada array, el elemento encuentra el índice mínimo de la array P[] tal que la suma de la subarreglo sobre el rango [0, i] es al menos arr[i]

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar encontrando la array de suma de prefijos de P[] y luego usando la búsqueda binaria para encontrar la suma cuyo valor es al menos arr[i] . Siga los pasos a continuación para resolver el problema:

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the lower bound
// of N using binary search
int binarySeach(vector<int> P, int N)
{
     
    // Stores the lower bound
    int i = 0;
 
    // Stores the upper bound
    int j = P.size() - 1;
 
    // Stores the minimum index
    // having value is at least N
    int index = -1;
 
    // Iterator while i<=j
    while (i <= j)
    {
         
        // Stores the mid index
        // of the range [i, j]
        int mid = i + (j - i) / 2;
 
        // If P[mid] is at least N
        if (P[mid] >= N)
        {
             
            // Update the value of
            // mid to index
            index = mid;
 
            // Update the value of j
            j = mid - 1;
        }
 
        // Update the value of i
        else
        {
            i = mid + 1;
        }
    }
 
    // Return the resultant index
    return index;
}
 
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
void minDays(vector<int> P, vector<int> arr)
{
     
    // Traverse the array P[]
    for(int i = 1; i < P.size(); i++)
    {
         
        // Find the prefix sum
        P[i] += P[i] + P[i - 1];
    }
 
    // Traverse the array arr[]
    for(int i = 0; i < arr.size(); i++)
    {
         
        // Find the minimum index of
        // the array having value
        // at least arr[i]
        int index = binarySeach(P, arr[i]);
 
        // If the index is not -1
        if (index != -1)
        {
            cout << index + 1 << " ";
        }
 
        // Otherwise
        else
        {
            cout << -1 << " ";
        }
    }
}
 
// Driver Code
int main()
{
    vector<int> arr = { 400, 200, 700, 900, 1400 };
    vector<int> P = { 100, 300, 400, 500, 600 };
    minDays(P, arr);
     
    return 0;
}
 
// This code is contributed by nirajgusain5

Java

// Java program for the above approach
 
public class GFG {
 
    // Function to find the minimum number
    // of days required to work to at least
    // arr[i] points for every array element
    static void minDays(int[] P, int[] arr)
    {
        // Traverse the array P[]
        for (int i = 1; i < P.length; i++) {
 
            // Find the prefix sum
            P[i] += P[i] + P[i - 1];
        }
 
        // Traverse the array arr[]
        for (int i = 0;
             i < arr.length; i++) {
 
            // Find the minimum index of
            // the array having value
            // at least arr[i]
            int index = binarySeach(
                P, arr[i]);
 
            // If the index is not -1
            if (index != -1) {
                System.out.print(
                    index + 1 + " ");
            }
 
            // Otherwise
            else {
                System.out.print(
                    -1 + " ");
            }
        }
    }
 
    // Function to find the lower bound
    // of N using binary search
    static int binarySeach(
        int[] P, int N)
    {
        // Stores the lower bound
        int i = 0;
 
        // Stores the upper bound
        int j = P.length - 1;
 
        // Stores the minimum index
        // having value is at least N
        int index = -1;
 
        // Iterator while i<=j
        while (i <= j) {
 
            // Stores the mid index
            // of the range [i, j]
            int mid = i + (j - i) / 2;
 
            // If P[mid] is at least N
            if (P[mid] >= N) {
 
                // Update the value of
                // mid to index
                index = mid;
 
                // Update the value of j
                j = mid - 1;
            }
 
            // Update the value of i
            else {
                i = mid + 1;
            }
        }
 
        // Return the resultant index
        return index;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 400, 200, 700, 900, 1400 };
        int[] P = { 100, 300, 400, 500, 600 };
        minDays(P, arr);
    }
}

Python3

# Python3 program for the above approach
 
# Function to find the minimum number
# of days required to work to at least
# arr[i] points for every array element
def minDays(P, arr):
 
    # Traverse the array P[]
    for i in range(1, len(P)):
       
        # Find the prefix sum
        P[i] += P[i] + P[i - 1]
 
    # Traverse the array arr[]
    for i in range(len(arr)):
       
        # Find the minimum index of
        # the array having value
        # at least arr[i]
        index = binarySeach(P, arr[i])
 
        # If the index is not -1
        if (index != -1):
            print(index + 1, end = " ")
        # Otherwise
        else:
            print(-1, end = " ")
 
# Function to find the lower bound
# of N using binary search
def binarySeach(P, N):
 
    # Stores the lower bound
    i = 0
 
    # Stores the upper bound
    j = len(P) - 1
 
    # Stores the minimum index
    # having value is at least N
    index = -1
 
    # Iterator while i<=j
    while (i <= j):
 
        # Stores the mid index
        # of the range [i, j]
        mid = i + (j - i) // 2
 
        # If P[mid] is at least N
        if (P[mid] >= N):
 
            # Update the value of
            # mid to index
            index = mid
 
            # Update the value of j
            j = mid - 1
 
        # Update the value of i
        else:
            i = mid + 1
 
    # Return the resultant index
    return index
 
    # Driver Code
if __name__ == '__main__':
    arr = [400, 200, 700,900,1400 ]
    P =  [100, 300, 400, 500, 600 ]
    minDays(P, arr)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
static void minDays(int[] P, int[] arr)
{
     
    // Traverse the array P[]
    for(int i = 1; i < P.Length; i++)
    {
         
        // Find the prefix sum
        P[i] += P[i] + P[i - 1];
    }
     
    // Traverse the array arr[]
    for(int i = 0; i < arr.Length; i++)
    {
         
        // Find the minimum index of
        // the array having value
        // at least arr[i]
        int index = binarySeach(P, arr[i]);
         
        // If the index is not -1
        if (index != -1)
        {
            Console.Write(index + 1 + " ");
        }
         
        // Otherwise
        else
        {
            Console.Write(-1 + " ");
        }
    }
}
 
// Function to find the lower bound
// of N using binary search
static int binarySeach(int[] P, int N)
{
     
    // Stores the lower bound
    int i = 0;
     
    // Stores the upper bound
    int j = P.Length - 1;
     
    // Stores the minimum index
    // having value is at least N
    int index = -1;
     
    // Iterator while i<=j
    while (i <= j)
    {
         
        // Stores the mid index
        // of the range [i, j]
        int mid = i + (j - i) / 2;
         
        // If P[mid] is at least N
        if (P[mid] >= N)
        {
             
            // Update the value of
            // mid to index
            index = mid;
             
            // Update the value of j
            j = mid - 1;
        }
         
        // Update the value of i
        else
        {
            i = mid + 1;
        }
    }
     
    // Return the resultant index
    return index;
}
 
// Driver Code
public static void Main(string[] args)
{
    int[] arr = { 400, 200, 700, 900, 1400 };
    int[] P = { 100, 300, 400, 500, 600 };
     
    minDays(P, arr);
}
}
     
// This code is contributed by ukasp

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the lower bound
// of N using binary search
function binarySeach(P, N)
{
     
    // Stores the lower bound
    var i = 0;
 
    // Stores the upper bound
    var j = P.length - 1;
 
    // Stores the minimum index
    // having value is at least N
    var index = -1;
 
    // Iterator while i<=j
    while (i <= j)
    {
         
        // Stores the mid index
        // of the range [i, j]
        var mid = i + parseInt((j - i) / 2);
 
        // If P[mid] is at least N
        if (P[mid] >= N)
        {
             
            // Update the value of
            // mid to index
            index = mid;
 
            // Update the value of j
            j = mid - 1;
        }
 
        // Update the value of i
        else
        {
            i = mid + 1;
        }
    }
 
    // Return the resultant index
    return index;
}
 
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
function minDays(P, arr)
{
     
    // Traverse the array P[]
    for(var i = 1; i < P.length; i++)
    {
         
        // Find the prefix sum
        P[i] += P[i] + P[i - 1];
    }
 
    // Traverse the array arr[]
    for(var i = 0; i < arr.length; i++)
    {
         
        // Find the minimum index of
        // the array having value
        // at least arr[i]
        var index = binarySeach(P, arr[i]);
 
        // If the index is not -1
        if (index != -1)
        {
            document.write( (index + 1) + " ");
        }
 
        // Otherwise
        else
        {
            document.write( -1 + " ");
        }
    }
}
 
// Driver Code
var arr = [400, 200, 700, 900, 1400];
var P = [100, 300, 400, 500, 600];
minDays(P, arr);
 
</script>
Producción: 

2 2 2 3 3

 

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *