Dada una array arr[] de N enteros y un costo entero , la tarea es calcular el costo de hacer que todos los elementos de la array sean 0 con la operación dada. En una sola operación, se puede elegir un índice 0 ≤ i < N y un entero X > 0 de modo que 0 ≤ i + X < N , entonces los elementos se pueden actualizar como arr[i] = arr[i] – 1 y arr[ yo + X] = arr[yo + X] + 1 . Si i + X ≥ N entonces solo se actualizará arr[i] pero con el doble del costo normal. Imprime el costo mínimo requerido.
Ejemplos:
Entrada: arr[] = {1, 2, 4, 5}, costo = 1
Salida: 31
Mover 1: i = 0, X = 3, arr[] = {0, 2, 4, 6} (costo = 1 )
Movimientos 2 y 3: i = 1, X = 2, arr[] = {0, 0, 4, 8} (coste = 2)
Movimientos 4, 5, 6 y 7: i = 2, X = 1, arr [] = {0, 0, 0, 12} (costo = 4)
Mover 8: i = 3, X > 0, arr[] = {0, 0, 0, 0} (costo = 24)
Costo total = 1 + 2 + 4 + 24 = 31
Entrada: arr[] = {1, 1, 0, 5}, costo = 2
Salida: 32
Enfoque: Para minimizar el costo, para cada índice siempre elijo X tal que i + X = N – 1, es decir, el último elemento, entonces el costo mínimo se puede calcular como:
- Almacene la suma de los elementos de arr[0] a arr[n – 2] en sum y luego actualice totalCost = cost * sum y arr[n – 1] = arr[n – 1] + sum .
- Ahora se ha calculado el coste de hacer todos los elementos 0 excepto el último. Y el costo de hacer que el último elemento sea 0 se puede calcular como totalCost = totalCost + (2 * cost * arr[n – 1]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum cost
int minCost(int n, int arr[], int cost)
{
int sum = 0, totalCost = 0;
// Sum of all the array elements
// except the last element
for (int i = 0; i < n - 1; i++)
sum += arr[i];
// Cost of making all the array elements 0
// except the last element
totalCost += cost * sum;
// Update the last element
arr[n - 1] += sum;
// Cost of making the last element 0
totalCost += (2 * cost * arr[n - 1]);
return totalCost;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int cost = 1;
cout << minCost(n, arr, cost);
}
Java
// Java implementation of the approach
public class GfG
{
// Function to return the minimum cost
static int minCost(int n, int arr[], int cost)
{
int sum = 0, totalCost = 0;
// Sum of all the array elements
// except the last element
for (int i = 0; i < n - 1; i++)
sum += arr[i];
// Cost of making all the array elements 0
// except the last element
totalCost += cost * sum;
// Update the last element
arr[n - 1] += sum;
// Cost of making the last element 0
totalCost += (2 * cost * arr[n - 1]);
return totalCost;
}
// Driver code
public static void main(String []args)
{
int arr[] = { 1, 2, 4, 5 };
int n = arr.length;
int cost = 1;
System.out.println(minCost(n, arr, cost));
}
}
// This code is contributed by Rituraj Jain
Python3
# Python3 implementation of the approach # Function to return the minimum cost def minCost(n, arr, cost): Sum, totalCost = 0, 0 # Sum of all the array elements # except the last element for i in range(0, n - 1): Sum += arr[i] # Cost of making all the array elements 0 # except the last element totalCost += cost * Sum # Update the last element arr[n - 1] += Sum # Cost of making the last element 0 totalCost += (2 * cost * arr[n - 1]) return totalCost # Driver code if __name__ == "__main__": arr = [1, 2, 4, 5] n = len(arr) cost = 1 print(minCost(n, arr, cost)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System ;
class GfG
{
// Function to return the minimum cost
static int minCost(int n, int []arr, int cost)
{
int sum = 0, totalCost = 0;
// Sum of all the array elements
// except the last element
for (int i = 0; i < n - 1; i++)
sum += arr[i];
// Cost of making all the array elements 0
// except the last element
totalCost += cost * sum;
// Update the last element
arr[n - 1] += sum;
// Cost of making the last element 0
totalCost += (2 * cost * arr[n - 1]);
return totalCost;
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 4, 5 };
int n = arr.Length;
int cost = 1;
Console.WriteLine(minCost(n, arr, cost));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the minimum cost
function minCost($n, $arr, $cost)
{
$sum = 0;
$totalCost = 0;
// Sum of all the array elements
// except the last element
for ($i = 0; $i < ($n - 1); $i++)
$sum += $arr[$i];
// Cost of making all the array
// elements 0 except the last element
$totalCost += $cost * $sum;
// Update the last element
$arr[$n - 1] += $sum;
// Cost of making the last element 0
$totalCost += (2 * $cost * $arr[$n - 1]);
return $totalCost;
}
// Driver code
$arr = array( 1, 2, 4, 5 );
$n = sizeof($arr);
$cost = 1;
echo minCost($n, $arr, $cost);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum cost
function minCost(n, arr, cost)
{
let sum = 0, totalCost = 0;
// Sum of all the array elements
// except the last element
for (let i = 0; i < n - 1; i++)
sum += arr[i];
// Cost of making all the array elements 0
// except the last element
totalCost += cost * sum;
// Update the last element
arr[n - 1] += sum;
// Cost of making the last element 0
totalCost += (2 * cost * arr[n - 1]);
return totalCost;
}
let arr = [ 1, 2, 4, 5 ];
let n = arr.length;
let cost = 1;
document.write(minCost(n, arr, cost));
</script>
31
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA