Dada una array arr[], de tamaño N y un número entero S , la tarea es encontrar las operaciones mínimas para hacer que la suma de la array sea menor o igual que S. En cada operación:
- Se puede elegir cualquier elemento y se puede decrementar en 1, o
- Puede ser reemplazado por cualquier otro elemento de la array.
Ejemplos:
Entrada: arr[]= {1, 2, 1 ,3, 1 ,2, 1}, S= 8
Salida: 2
Explicación: Inicialmente la suma de la array es 11.
Ahora disminuya 1 en el índice 0 a 0 y reemplace 3 por 0.
La suma se convierte en 7 < 8. Entonces 2 operaciones.Entrada: arr[] = {1,2,3,4}, S= 11
Salida: 0
Explicación: La suma ya es < =11, por lo que 0 operaciones.
Enfoque: este problema se puede resolver utilizando el enfoque codicioso y la suma de sufijos ordenando la array. Aplicar la primera operación en el elemento mínimo cualquier cantidad de veces y luego aplicar la segunda operación en los sufijos reemplazándolo con el elemento mínimo después de la primera operación da las operaciones mínimas.
Primero ordena la array. Considere realizar x operaciones de primer tipo en arr[0] y luego realizar la segunda operación en el sufijo de la array de longitud i . Considere también que la suma de este sufijo de longitud i es sufSum .
La suma de la array modificada debe ser <=S
Entonces, la diferencia a restar de la suma debe ser (diff)>= sum – S.Si se realizan x operaciones de tipo 1 en el elemento mínimo y las operaciones de tipo 2 se realizan en el sufijo de la array de [i, n), la suma de la array disminuida es
costo = x + s – (ni) * (a[0] – x)
costo = (n-i+1)* x-(ni)* a[0] +s
costo >= suma – S = diff
s – (ni) * a[0] + (n-i+1) *x >= diferencia
entonces x >= (diferencia – s+(ni)* a[0]) / (n-i+1)El valor mínimo de x es x = ceil((diff -s+ (ni)* a[0]) / (n-i+1))
Entonces las operaciones totales son x (tipo-1) + (ni) tipo-2
Siga estos pasos para resolver los problemas anteriores:
- Inicialice una variable sum = 0 y el tamaño de la array en N .
- Iterar a través del vector y encontrar la suma de la array.
- Si suma < = S imprime 0 y regresa.
- Ordene el vector y asigne diff = sum-S .
- Inicializar ops = sum-S que es el máximo de operaciones posibles.
- Inicialice s =0 que almacena la suma del sufijo del vector.
- Ahora recorra desde el final del vector usando for loop.
- Mantenga un registro de la suma del sufijo en la variable s .
- Inicialice una variable dec que es el valor que se decrementará del sufijo de la array
- Si s-dec es mayor o igual que diff , no hay necesidad de decrementar arr[0], así que asigne x =0 .
- De lo contrario, encuentre el valor de x , que es el valor que se decrementará en arr[0] y encuentre las operaciones mínimas.
- Imprimir las operaciones mínimas
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 divide and get the ceil value
int ceil_div(int a, int b)
{
return a / b + ((a ^ b) > 0 && a % b);
}
// Function to find the minimum cost
void minimum_cost(vector<int> arr, int S)
{
int sum = 0;
int n = arr.size();
// Find the sum of the array
for (int i = 0; i < arr.size(); i++) {
sum += arr[i];
}
// If sum <= S no operations required
if (sum <= S) {
cout << 0 << endl;
return;
}
// Sort the array
sort(arr.begin(), arr.end());
int diff = sum - S;
// Maximum it requires sum-S operations
// by decrementing
// the arr[0] by 1
int ops = sum - S;
// suffix sum
int s = 0;
int x;
for (int i = n - 1; i > 0; i--) {
s += arr[i];
// If replacing the last elements
// with doing the first operation
// x = 0 Decrementing the a[i] from
// the suffix [i,n-1]
int dec = (n - i) * arr[0];
if (s - dec >= diff) {
x = 0;
}
// Find how times the first element
// should be decremented by 1 and
// incremented by 1 which is x
else {
x = max(ceil_div((diff - s + dec),
(n - i + 1)), 0);
}
// First operation + second operation
if (x + n - i < ops) {
ops = x + n - i;
}
}
// Print the operations
cout << ops << endl;
}
// Driver code
int main()
{
// Initialize the array
vector<int> arr = { 1, 2, 1, 3, 1, 2, 1 };
int S = 8;
// Function call
minimum_cost(arr, S);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG {
// Function to divide and get the ceil value
static int ceil_div(int a, int b) {
int temp = 0;
if (((a ^ b) > 0) && ((a % b) > 0)) {
temp = 1;
}
return (a / b) + temp;
}
// Function to find the minimum cost
static void minimum_cost(int[] arr, int S) {
int sum = 0;
int n = arr.length;
// Find the sum of the array
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
// If sum <= S no operations required
if (sum <= S) {
System.out.println(0);
return;
}
// Sort the array
Arrays.sort(arr);
int diff = sum - S;
// Maximum it requires sum-S operations
// by decrementing
// the arr[0] by 1
int ops = sum - S;
// suffix sum
int s = 0;
int x;
for (int i = n - 1; i > 0; i--) {
s += arr[i];
// If replacing the last elements
// with doing the first operation
// x = 0 Decrementing the a[i] from
// the suffix [i,n-1]
int dec = (n - i) * arr[0];
if (s - dec >= diff) {
x = 0;
}
// Find how times the first element
// should be decremented by 1 and
// incremented by 1 which is x
else {
x = Math.max(ceil_div((diff - s + dec),
(n - i + 1)), 0);
}
// First operation + second operation
if (x + n - i < ops) {
ops = x + n - i;
}
}
// Print the operations
System.out.println(ops);
}
// Driver code
public static void main(String args[])
{
// Initialize the array
int[] arr = { 1, 2, 1, 3, 1, 2, 1 };
int S = 8;
// Function call
minimum_cost(arr, S);
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python 3 program for the above approach # Function to divide and get the ceil value def ceil_div(a, b): return a // b + ((a ^ b) > 0 and a % b) # Function to find the minimum cost def minimum_cost(arr, S): sum = 0 n = len(arr) # Find the sum of the array for i in range(len(arr)): sum += arr[i] # If sum <= S no operations required if (sum <= S): print(0) return # Sort the array arr.sort() diff = sum - S # Maximum it requires sum-S operations # by decrementing # the arr[0] by 1 ops = sum - S # suffix sum s = 0 for i in range(n - 1, -1, -1): s += arr[i] # If replacing the last elements # with doing the first operation # x = 0 Decrementing the a[i] from # the suffix [i,n-1] dec = (n - i) * arr[0] if (s - dec >= diff): x = 0 # Find how times the first element # should be decremented by 1 and # incremented by 1 which is x else: x = max(ceil_div((diff - s + dec), (n - i + 1)), 0) # First operation + second operation if (x + n - i < ops): ops = x + n - i # Print the operations print(ops) # Driver code if __name__ == "__main__": # Initialize the array arr = [1, 2, 1, 3, 1, 2, 1] S = 8 # Function call minimum_cost(arr, S) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to divide and get the ceil value
static int ceil_div(int a, int b) {
int temp = 0;
if (((a ^ b) > 0) && ((a % b) > 0)) {
temp = 1;
}
return (a / b) + temp;
}
// Function to find the minimum cost
static void minimum_cost(int[] arr, int S) {
int sum = 0;
int n = arr.Length;
// Find the sum of the array
for (int i = 0; i < arr.Length; i++) {
sum += arr[i];
}
// If sum <= S no operations required
if (sum <= S) {
Console.WriteLine(0);
return;
}
// Sort the array
Array.Sort(arr);
int diff = sum - S;
// Maximum it requires sum-S operations
// by decrementing
// the arr[0] by 1
int ops = sum - S;
// suffix sum
int s = 0;
int x;
for (int i = n - 1; i > 0; i--) {
s += arr[i];
// If replacing the last elements
// with doing the first operation
// x = 0 Decrementing the a[i] from
// the suffix [i,n-1]
int dec = (n - i) * arr[0];
if (s - dec >= diff) {
x = 0;
}
// Find how times the first element
// should be decremented by 1 and
// incremented by 1 which is x
else {
x = Math.Max(ceil_div((diff - s + dec),
(n - i + 1)), 0);
}
// First operation + second operation
if (x + n - i < ops) {
ops = x + n - i;
}
}
// Print the operations
Console.Write(ops);
}
// Driver code
public static void Main()
{
// Initialize the array
int[] arr = { 1, 2, 1, 3, 1, 2, 1 };
int S = 8;
// Function call
minimum_cost(arr, S);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to divide and get the ceil value
const ceil_div = (a, b) => parseInt(a / b) + ((a ^ b) > 0 && a % b);
// Function to find the minimum cost
const minimum_cost = (arr, S) => {
let sum = 0;
let n = arr.length;
// Find the sum of the array
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
// If sum <= S no operations required
if (sum <= S) {
document.write("0<br/>");
return;
}
// Sort the array
arr.sort();
let diff = sum - S;
// Maximum it requires sum-S operations
// by decrementing
// the arr[0] by 1
let ops = sum - S;
// suffix sum
let s = 0;
let x;
for (let i = n - 1; i > 0; i--) {
s += arr[i];
// If replacing the last elements
// with doing the first operation
// x = 0 Decrementing the a[i] from
// the suffix [i,n-1]
let dec = (n - i) * arr[0];
if (s - dec >= diff) {
x = 0;
}
// Find how times the first element
// should be decremented by 1 and
// incremented by 1 which is x
else {
x = Math.max(ceil_div((diff - s + dec),
(n - i + 1)), 0);
}
// First operation + second operation
if (x + n - i < ops) {
ops = x + n - i;
}
}
// Print the operations
document.write(`${ops}<br/>`);
}
// Driver code
// Initialize the array
let arr = [1, 2, 1, 3, 1, 2, 1];
let S = 8;
// Function call
minimum_cost(arr, S);
// This code is contributed by rakeshsahni
</script>
2
Complejidad de tiempo: O(N* logN)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA