Dados dos enteros X , K , y dos arrays arr[] y R[], ambas formadas por N enteros positivos donde R[i] indica la cantidad por la que arr[i] aumenta en un día, la tarea es encontrar el número mínimo de días después de los cuales la suma de los elementos de la array que tienen un valor mayor o igual a K se convierte en al menos X .
Ejemplos:
Entrada: X = 100, K = 45, arr[] = {2, 5, 2, 6}, R[] = {10, 13, 15, 12}
Salida: 4
Explicación:
Considere los siguientes valores de array después de cada día:
- Día 1: después del día 1, todos los elementos de la array se modifican a {12, 18, 17, 18}. La suma de los elementos que tienen valores >= K(= 45) es 0.
- Día 2: después del día 2, todos los elementos de la array se modifican a {22, 31, 32, 30}. La suma de los elementos que tienen valores >= K(= 45) es 0.
- Día 3: después del día 3, todos los elementos de la array se modifican a {32, 44, 47, 42}. La suma de los elementos que tienen valores >= K(= 45) es 47.
- Día 4: después del día 4, todos los elementos de la array se modifican a {42, 57, 62, 54}. La suma de los elementos que tienen valores >= K(= 45) es 57 + 62 + 54 = 167, que es al menos X(= 100).
Por lo tanto, el número mínimo de días necesarios es de 4.
Entrada: X = 65, K = 10, arr[] = {1, 1, 1, 1, 3}, R[] = {2, 1, 2, 2, 1}
Salida: 9
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es seguir incrementando la cantidad de días y cada vez que la suma de los elementos de la array que tienen un valor de al menos K sea mayor o igual a X . Después de incrementar por D días, imprime el valor del número actual de días obtenidos.
Complejidad temporal: O(N*X)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos bajo como 0 y alto como X .
- Inicialice una variable, digamos minDays que almacena la cantidad mínima de días.
- Iterar hasta que el valor de low sea como máximo alto y realizar los siguientes pasos:
- Inicialice una variable mid como low + (high – low)/2 y variable, diga sum como 0 para almacenar la suma de los elementos de la array después de la mitad de la cantidad de días.
- Recorra el arreglo , arr[] usando la variable i y realice los siguientes pasos:
- Inicialice una variable temporal como (arr[i] + R[i]*mid) .
- Si el valor de temp no es menor que K , agregue el valor de temp a sum .
- Si el valor de sum es al menos X , actualice el valor de minDays a mid y el valor de high a (mid – 1) .
- De lo contrario, actualice el valor de bajo a (medio + 1) .
- Después de completar los pasos anteriores, imprima el valor de minDays como el número mínimo de días resultante.
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 minimum number
// of days such that the sum of array
// elements >= K is at least X
void findMinDays(int arr[], int R[],
int N, int X, int K)
{
// Initialize the boundaries of
// search space
int low = 0, high = X;
int minDays;
// Perform the binary search
while (low <= high) {
// Find the value of mid
int mid = (low + high) / 2;
int sum = 0;
// Traverse the array, arr[]
for (int i = 0; i < N; i++) {
// Find the value of arr[i]
// after mid number of days
int temp = arr[i] + R[i] * mid;
// Check if temp is not
// less than K
if (temp >= K) {
// Update the value
// of sum
sum += temp;
}
}
// Check if the value of sum
// is greater than X
if (sum >= X) {
// Update value of high
minDays = mid;
high = mid - 1;
}
// Update the value of low
else {
low = mid + 1;
}
}
// Print the minimum number
// of days
cout << minDays;
}
// Driver Code
int main()
{
int X = 100, K = 45;
int arr[] = { 2, 5, 2, 6 };
int R[] = { 10, 13, 15, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
findMinDays(arr, R, N, X, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the minimum number
// of days such that the sum of array
// elements >= K is at least X
static void findMinDays(int arr[], int R[], int N,
int X, int K)
{
// Initialize the boundaries of
// search space
int low = 0, high = X;
int minDays = -1;
// Perform the binary search
while (low <= high)
{
// Find the value of mid
int mid = (low + high) / 2;
int sum = 0;
// Traverse the array, arr[]
for(int i = 0; i < N; i++)
{
// Find the value of arr[i]
// after mid number of days
int temp = arr[i] + R[i] * mid;
// Check if temp is not
// less than K
if (temp >= K)
{
// Update the value
// of sum
sum += temp;
}
}
// Check if the value of sum
// is greater than X
if (sum >= X)
{
// Update value of high
minDays = mid;
high = mid - 1;
}
// Update the value of low
else
{
low = mid + 1;
}
}
// Print the minimum number
// of days
System.out.println(minDays);
}
// Driver Code
public static void main(String[] args)
{
int X = 100, K = 45;
int arr[] = { 2, 5, 2, 6 };
int R[] = { 10, 13, 15, 12 };
int N = arr.length;
findMinDays(arr, R, N, X, K);
}
}
// This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum number
// of days such that the sum of array
// elements >= K is at least X
static void findMinDays(int[] arr, int[] R, int N,
int X, int K)
{
// Initialize the boundaries of
// search space
int low = 0, high = X;
int minDays = -1;
// Perform the binary search
while (low <= high) {
// Find the value of mid
int mid = (low + high) / 2;
int sum = 0;
// Traverse the array, arr[]
for (int i = 0; i < N; i++) {
// Find the value of arr[i]
// after mid number of days
int temp = arr[i] + R[i] * mid;
// Check if temp is not
// less than K
if (temp >= K) {
// Update the value
// of sum
sum += temp;
}
}
// Check if the value of sum
// is greater than X
if (sum >= X) {
// Update value of high
minDays = mid;
high = mid - 1;
}
// Update the value of low
else {
low = mid + 1;
}
}
// Print the minimum number
// of days
Console.Write(minDays);
}
// Driver Code
public static void Main(string[] args)
{
int X = 100, K = 45;
int[] arr = { 2, 5, 2, 6 };
int[] R = { 10, 13, 15, 12 };
int N = arr.Length;
findMinDays(arr, R, N, X, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of days such that the sum of array
// elements >= K is at least X
function findMinDays(arr, R, N, X, K) {
// Initialize the boundaries of
// search space
let low = 0, high = X;
let minDays;
// Perform the binary search
while (low <= high) {
// Find the value of mid
let mid = Math.floor((low + high) / 2);
let sum = 0;
// Traverse the array, arr[]
for (let i = 0; i < N; i++) {
// Find the value of arr[i]
// after mid number of days
let temp = arr[i] + R[i] * mid;
// Check if temp is not
// less than K
if (temp >= K) {
// Update the value
// of sum
sum += temp;
}
}
// Check if the value of sum
// is greater than X
if (sum >= X) {
// Update value of high
minDays = mid;
high = mid - 1;
}
// Update the value of low
else {
low = mid + 1;
}
}
// Print the minimum number
// of days
document.write(minDays);
}
// Driver Code
let X = 100, K = 45;
let arr = [2, 5, 2, 6];
let R = [10, 13, 15, 12];
let N = arr.length
findMinDays(arr, R, N, X, K);
// This code is contributed by _saurabh_jaiswal.
</script>
Python3
# Python 3 program for the above approach # Function to find the minimum number # of days such that the sum of array # elements >= K is at least X def findMinDays(arr, R, N, X, K): # Initialize the boundaries of # search space low = 0 high = X minDays = 0 # Perform the binary search while (low <= high): # Find the value of mid mid = (low + high) // 2 sum = 0 # Traverse the array, arr[] for i in range(N): # Find the value of arr[i] # after mid number of days temp = arr[i] + R[i] * mid # Check if temp is not # less than K if (temp >= K): # Update the value # of sum sum += temp # Check if the value of sum # is greater than X if (sum >= X): # Update value of high minDays = mid high = mid - 1 # Update the value of low else: low = mid + 1 # Print the minimum number # of days print(minDays) # Driver Code if __name__ == '__main__': X = 100 K = 45 arr = [2, 5, 2, 6] R = [10, 13, 15, 12] N = len(arr) findMinDays(arr, R, N, X, K) # This code is contributed by SURENDRA_GANGWAR.
Producción:
4
Complejidad de tiempo: O(N*log X)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por himankgoel12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA