Dada una array arr[] y un entero K , la tarea es encontrar el número mínimo de operaciones requeridas para cambiar una array B de tamaño N que contenga todos ceros de modo que cada elemento de B sea mayor o igual que arr. es decir, arr[i] >= B[i]. En cualquier operación, puede elegir un subarreglo de B de tamaño K e incrementar todos los elementos del subarreglo en 1.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 2
Salida: 9
Explicación:
Al principio B[] = {0, 0, 0, 0, 0} operaciones = 0
Incrementar subarreglo a[ 1:2] por 1 => B = {1, 1, 0, 0, 0}, operaciones = 1
Incrementar el subarreglo a[2:3] por 1 => B = {1, 2, 1, 0, 0} , operaciones = 2
Incrementar el subarreglo a[3:4] en 2 => B = {1, 2, 3, 2, 0}, operaciones = 4
Incrementar el subarreglo a[4:5] en 5 => B = {1, 2, 3, 7, 5}, operaciones = 9
Por lo tanto, el número de tales operaciones requeridas es 9.Entrada: arr[] = {2, 3, 1}, K = 3
Salida: 3
Explicación:
Incrementar la array completa en 3
Enfoque: La idea es incrementar el subarreglo de tamaño K siempre que B[i] sea menor que arr[i] y también incrementar el conteo de tales operaciones en 1 en cada paso. Para incrementar el subarreglo de tamaño K, use el arreglo de diferencias para la actualización de consulta de rango en O(1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum number of operations
// required to change an array of
// all zeros such that every element
// is greater than the given array
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// number of operations required
// to change all the array of zeros
// such that every element is greater
// than the given array
int find_minimum_operations(int n, int b[],
int k)
{
// Declaring the difference
// array of size N
int d[n + 1] = {0};
// Number of operations
int operations = 0, need;
for(int i = 0; i < n; i++)
{
// First update the D[i] value
// with the previous value
if (i > 0)
{
d[i] += d[i - 1];
}
// The index i has to be incremented
if (b[i] > d[i])
{
// We have to perform
// (b[i]-d[i]) operations more
operations += b[i] - d[i];
need = b[i] - d[i];
// Increment the range
// i to i + k by need
d[i] += need;
// Check if i + k is valid index
if(i + k <= n)
{
d[i + k]-= need;
}
}
}
cout << operations << endl;
}
// Driver Code
int main()
{
int n = 5;
int b[] = { 1, 2, 3, 4, 5 };
int k = 2;
// Function Call
find_minimum_operations(n, b, k);
return 0;
}
// This code is contributed by shubhamsingh10
Java
// Java implementation to find the
// minimum number of operations
// required to change an array of
// all zeros such that every element
// is greater than the given array
class GFG{
// Function to find the minimum
// number of operations required
// to change all the array of zeros
// such that every element is greater
// than the given array
static void find_minimum_operations(int n, int b[],
int k)
{
// Declaring the difference
// array of size N
int d[] = new int[n + 1];
// Number of operations
int i, operations = 0, need;
for(i = 0; i < n; i++)
{
// First update the D[i] value
// with the previous value
if (i > 0)
{
d[i] += d[i - 1];
}
// The index i has to be incremented
if (b[i] > d[i])
{
// We have to perform
// (b[i]-d[i]) operations more
operations += b[i] - d[i];
need = b[i] - d[i];
// Increment the range
// i to i + k by need
d[i] += need;
// Check if i + k is valid index
if(i + k <= n)
{
d[i + k]-= need;
}
}
}
System.out.println(operations);
}
// Driver Code
public static void main (String []args)
{
int n = 5;
int b[] = { 1, 2, 3, 4, 5 };
int k = 2;
// Function Call
find_minimum_operations(n, b, k);
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation to find the # minimum number of operations required # to change an array of all zeros # such that every element is greater than # the given array # Function to find the minimum # number of operations required # to change all the array of zeros # such that every element is greater # than the given array def find_minimum_operations(n, b, k): # Declaring the difference # array of size N d =[0 for i in range(n + 1)] # Number of operations operations = 0 for i in range(n): # First update the D[i] value with # the previous value d[i]+= d[i-1] # The index i has to be incremented if b[i]>d[i]: # We have to perform # (b[i]-d[i]) operations more operations+=(b[i]-d[i]) need =(b[i]-d[i]) # Increment the range # i to i + k by need d[i]+= need # Check if i + k is valid index if i + k<= n: d[i + k]-= need return operations # Driver Code if __name__ == "__main__": n = 5 b =[1, 2, 3, 4, 5] k = 2 # Function Call print(find_minimum_operations(n, b, k))
C#
// C# implementation to find the
// minimum number of operations
// required to change an array of
// all zeros such that every element
// is greater than the given array
using System;
class GFG{
// Function to find the minimum
// number of operations required
// to change all the array of zeros
// such that every element is greater
// than the given array
static void find_minimum_operations(int n, int[] b,
int k)
{
// Declaring the difference
// array of size N
int[] d = new int[n + 1];
// Number of operations
int i, operations = 0, need;
for(i = 0; i < n; i++)
{
// First update the D[i] value
// with the previous value
if (i > 0)
{
d[i] += d[i - 1];
}
// The index i has to be incremented
if (b[i] > d[i])
{
// We have to perform
// (b[i]-d[i]) operations more
operations += b[i] - d[i];
need = b[i] - d[i];
// Increment the range
// i to i + k by need
d[i] += need;
// Check if i + k is valid index
if(i + k <= n)
{
d[i + k]-= need;
}
}
}
Console.Write(operations);
}
// Driver Code
public static void Main (string []args)
{
int n = 5;
int[] b = { 1, 2, 3, 4, 5 };
int k = 2;
// Function Call
find_minimum_operations(n, b, k);
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript implementation to find the
// minimum number of operations
// required to change an array of
// all zeros such that every element
// is greater than the given array
// Function to find the minimum
// number of operations required
// to change all the array of zeros
// such that every element is greater
// than the given array
function find_minimum_operations(n, b, k)
{
// Declaring the difference
// array of size N
let d = new Array(n + 1);
d.fill(0);
// Number of operations
let i, operations = 0, need;
for(i = 0; i < n; i++)
{
// First update the D[i] value
// with the previous value
if (i > 0)
{
d[i] += d[i - 1];
}
// The index i has to be incremented
if (b[i] > d[i])
{
// We have to perform
// (b[i]-d[i]) operations more
operations += b[i] - d[i];
need = b[i] - d[i];
// Increment the range
// i to i + k by need
d[i] += need;
// Check if i + k is valid index
if (i + k <= n)
{
d[i + k]-= need;
}
}
}
document.write(operations);
}
// Driver code
let n = 5;
let b = [ 1, 2, 3, 4, 5 ];
let k = 2;
// Function Call
find_minimum_operations(n, b, k);
// This code is contributed by divyesh072019
</script>
9
Complejidad temporal: O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA