Dada una array circular arr[] de N enteros y una array cost[] , la tarea es calcular el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean iguales a 0 , donde en cada operación disminuye el valor de un índice i por 1. Si el valor de un índice se vuelve 0, disminuya el valor de arr[i+1] por cost[i] , disminuya el valor de arr[i + 2] por cost[i + 1] y así sucesivamente.
Nota: si un elemento se vuelve menor que 0, se considera que es 0.
Ejemplo:
Entrada: arr[] = {7, 2, 5}, cost[] = {8, 9, 3}
Salida: 6
Explicación: Los decrementos se pueden hacer de la siguiente manera:
- Disminuye el valor de arr[1] dos veces. Por lo tanto, el valor de arr[2] será decrementado por el costo[1] y el valor de arr[0] será decrementado por el costo[2]. Por lo tanto, la array final será arr[] = {4, 0, 0}.
- Ahora, disminuya el valor de arr[0], 4 veces para convertirlo en 0. Por lo tanto, la array se convierte en arr[] = {0, 0, 0}.
Por lo tanto, el número de operaciones requeridas para hacer que todos los elementos de la array sean iguales a cero es 6, que es el mínimo posible.
Entrada: arr[] = {6, 7, 7, 10, 8, 2}, cost[] = {5, 10, 1, 4, 7, 7}
Salida: 16
Enfoque: El problema dado se puede resolver utilizando un enfoque codicioso mediante las siguientes observaciones:
- El último elemento restante distinto de cero de la array arr[] , supongamos que x requerirá x operaciones de decremento.
- Supongamos que después de las operaciones de decremento, el valor de arr[i] se vuelve 0 , luego para arr[i] , el número requerido de decrementos es arr[i] , para arr[i+1] , el número requerido de decrementos será arr [i+1] – max(0, arr[i+1] – costo[i]) y así sucesivamente.
A continuación se detallan los pasos a seguir:
- Recorre la array dada arr[] en el rango [0, N) usando una variable i .
- El número de operaciones requeridas para hacer que el i -ésimo índice de la array sea igual a cero es arr[i] – min(arr[i], cost[i-1]) . Por lo tanto, mantenga la suma de este valor sobre todos los índices en una variable ans .
- Incremente el valor de ans por el valor mínimo de arr[i] o cost[i] sobre todos los índices en el rango [0, N) .
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 minimum decrements
// required to make all array elements 0
int minDecrements(int arr[], int powr[], int N)
{
// Variable to store the answer
int ans = 0;
int mn = INT_MAX;
// Traverse the array
for (int i = 0; i < N; i++) {
int idx = (i + 1) % N;
int val = min(arr[idx], powr[i]);
ans += arr[idx] - val;
// Store the minimum one
mn = min(mn, val);
}
ans += mn;
// Return the ans
return ans;
}
// Driver Code
int main()
{
int arr[] = { 6, 7, 7, 10, 8, 2 };
int powr[] = { 5, 10, 1, 4, 7, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << minDecrements(arr, powr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find minimum decrements
// required to make all array elements 0
static int minDecrements(int []arr, int []powr, int N)
{
// Variable to store the answer
int ans = 0;
int mn = Integer.MAX_VALUE;
// Traverse the array
for (int i = 0; i < N; i++) {
int idx = (i + 1) % N;
int val = Math.min(arr[idx], powr[i]);
ans += arr[idx] - val;
// Store the minimum one
mn = Math.min(mn, val);
}
ans += mn;
// Return the ans
return ans;
}
// Driver Code
public static void main(String args[])
{
int []arr = { 6, 7, 7, 10, 8, 2 };
int []powr = { 5, 10, 1, 4, 7, 7 };
int N = arr.length;
System.out.println(minDecrements(arr, powr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program for the above approach # Function to find minimum decrements # required to make all array elements 0 def minDecrements(arr, powr, N): # Variable to store the answer ans = 0 mn = 99999999 # Traverse the array for i in range(N): idx = (i + 1) % N val = min(arr[idx], powr[i]) ans += arr[idx] - val # Store the minimum one mn = min(mn, val) ans += mn # Return the ans return ans # Driver Code if __name__ == "__main__": arr = [6, 7, 7, 10, 8, 2] powr = [5, 10, 1, 4, 7, 7] N = len(arr) print(minDecrements(arr, powr, N)) # This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG
{
// Function to find minimum decrements
// required to make all array elements 0
static int minDecrements(int []arr, int []powr, int N)
{
// Variable to store the answer
int ans = 0;
int mn = Int32.MaxValue;
// Traverse the array
for (int i = 0; i < N; i++) {
int idx = (i + 1) % N;
int val = Math.Min(arr[idx], powr[i]);
ans += arr[idx] - val;
// Store the minimum one
mn = Math.Min(mn, val);
}
ans += mn;
// Return the ans
return ans;
}
// Driver Code
public static void Main()
{
int []arr = { 6, 7, 7, 10, 8, 2 };
int []powr = { 5, 10, 1, 4, 7, 7 };
int N = arr.Length;
Console.Write(minDecrements(arr, powr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find minimum decrements
// required to make all array elements 0
function minDecrements(arr, powr, N)
{
// Variable to store the answer
let ans = 0;
let mn = Number.MAX_SAFE_INTEGER
// Traverse the array
for (let i = 0; i < N; i++) {
let idx = (i + 1) % N;
let val = Math.min(arr[idx], powr[i]);
ans += arr[idx] - val;
// Store the minimum one
mn = Math.min(mn, val);
}
ans += mn;
// Return the ans
return ans;
}
// Driver Code
let arr = [ 6, 7, 7, 10, 8, 2 ];
let powr = [ 5, 10, 1, 4, 7, 7 ];
let N = arr.length;
document.write(minDecrements(arr, powr, N));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
16
Complejidad temporal: O(N)
Espacio auxiliar: O(1)