Minimice la suma de cambios en Array de tal manera que la relación entre el nuevo elemento y la suma de la array sea como máximo p:q

Dada una array A de n enteros y dos enteros p y q, la tarea es aumentar algunos (o todos) los valores de la array A de tal manera que la relación de cada elemento (después del primer elemento) con respecto a la suma total de todos los elementos antes de que el elemento actual permanezca menor o igual a p / q . Devuelve la suma mínima de cambios a realizar.

Ejemplos:

Entrada : n = 4, A = {20100, 1, 202, 202}, p = 1, q = 100
Salida : 99
Explicación : 50 se agrega al primer elemento y 49 al segundo elemento, de modo que la array resultante se convierte en {20150, 50, 202, 202}.
50/20150 <= 1/100
202/(20150+50) <=1/100
202/(20150+50+202)<=1/100
Por lo tanto, la condición se cumple para todos los elementos y por lo tanto 50+49= 99 sería la respuesta. 
También hay otras respuestas posibles, pero necesitamos encontrar la suma mínima posible.

Entrada : n = 3, A = {1, 1, 1}, p = 100, q = 100
Salida : 0

 

Enfoque: El problema se puede resolver fácilmente utilizando los conceptos de suma de prefijos y búsqueda binaria

  • Se puede observar claramente que
    • si la condición establecida en el problema se logra para una cierta suma de cambios (digamos S ),
    • entonces siempre es posible lograr la condición para todos los números mayores que S y
    • no se puede lograr para todos los números menores que S.
    • Entonces, podemos aplicar la búsqueda binaria para encontrar la respuesta.
  • Además, se debe observar cuidadosamente que en lugar de distribuir S (suma de cambios) entre diferentes elementos, si solo lo agregamos al primer elemento, eso no afectaría la respuesta.

Por ejemplo, en el primer ejemplo anterior, si se agrega 99 al primer elemento, la array resultante aún cumplirá la condición requerida.

Siga los pasos a continuación para resolver el problema: 

  • Haga una array de suma de prefijos de la array dada.
  • Usando la búsqueda binaria en el rango 0 a INT_MAX, encuentre la respuesta mínima posible.

NOTA: La división puede generar errores y valores superpuestos. 

Entonces, en lugar de una comparación como (a/b)<=(c/d) , haremos (a*d)<=(b*c) .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for find minimum
// sum of changes in an array
#include <bits/stdc++.h>
using namespace std;
 
// function to check if the candidate sum
// satisfies the condition of the problem
bool isValid(int candidate, int pre[], int n, int A[],
             int p, int q)
{
    // flag variable to check wrong answer
    bool flag = true;
    for (int i = 1; i < n; i++) {
 
        // Now for each element, we are checking
        // if its ratio with sum of all previous
        // elements + candidate is greater than p/q.
        // If so, we will return false.
        int curr_sum = pre[i - 1] + candidate;
        if (A[i] * q > p * curr_sum) {
            flag = false;
            break;
        }
        // comparing like A[i]/(curr_sum)>p/q
        // will be error prone.
    }
    return flag;
}
 
int solve(int n, int A[], int p, int q)
{
 
    // declaring and constructing
    // prefix sum array
    int pre[n];
    pre[0] = A[0];
    for (int i = 1; i < n; i++) {
        pre[i] = A[i] + pre[i - 1];
    }
 
    // setting lower and upper bound for
    // binary search
    int lo = 0, hi = INT_MAX, ans = INT_MAX;
 
    // since minimum answer is needed,
    // so it is initialized with INT_MAX
    while (lo <= hi) {
 
        // calculating mid by using (lo+hi)/2
        // may overflow in certain cases
        int mid = lo + (hi - lo) / 2;
 
        // checking if required ratio would be
        // achieved by all elements if "mid" is
        // considered as answer
        if (isValid(mid, pre, n, A, p, q)) {
            ans = mid;
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }
    return ans;
}
 
// Driver Function
int main()
{
    int n, p, q;
    n = 4, p = 1, q = 100;
    int A[] = { 20100, 1, 202, 202 };
 
    // printing the required answer
    cout << solve(n, A, p, q) << endl;
}

Java

// Java program for find minimum
// sum of changes in an arraykage whatever //do not write package name here */
import java.io.*;
 
class GFG {
 
  // function to check if the candidate sum
  // satisfies the condition of the problem
  static Boolean isValid(int candidate, int pre[], int n, int A[],
                         int p, int q)
  {
     
    // flag variable to check wrong answer
    Boolean flag = true;
    for (int i = 1; i < n; i++) {
 
      // Now for each element, we are checking
      // if its ratio with sum of all previous
      // elements + candidate is greater than p/q.
      // If so, we will return false.
      int curr_sum = pre[i - 1] + candidate;
      if (A[i] * q > p * curr_sum) {
        flag = false;
        break;
      }
      // comparing like A[i]/(curr_sum)>p/q
      // will be error prone.
    }
    return flag;
  }
 
  static int solve(int n, int A[], int p, int q)
  {
 
    // declaring and constructing
    // prefix sum array
    int pre[] = new int[n];
    pre[0] = A[0];
    for (int i = 1; i < n; i++) {
      pre[i] = A[i] + pre[i - 1];
    }
 
    // setting lower and upper bound for
    // binary search
    int lo = 0, hi = Integer.MAX_VALUE, ans = Integer.MAX_VALUE;
 
    // since minimum answer is needed,
    // so it is initialized with INT_MAX
    while (lo <= hi) {
 
      // calculating mid by using (lo+hi)/2
      // may overflow in certain cases
      int mid = lo + (hi - lo) / 2;
 
      // checking if required ratio would be
      // achieved by all elements if "mid" is
      // considered as answer
      if (isValid(mid, pre, n, A, p, q)) {
        ans = mid;
        hi = mid - 1;
      }
      else {
        lo = mid + 1;
      }
    }
    return ans;
  }
 
  // Driver Function
  public static void main (String[] args)
  {
    int n = 4, p = 1, q = 100;
    int A[] = { 20100, 1, 202, 202 };
 
    // printing the required answer
    System.out.println(solve(n, A, p, q));
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# Python code for the above approach
import sys
 
# function to check if the candidate sum
# satisfies the condition of the problem
def isValid(candidate, pre, n, A, p, q) :
     
    # flag variable to check wrong answer
    flag = True
    for i in range(1, n) :
  
        # Now for each element, we are checking
        # if its ratio with sum of all previous
        # elements + candidate is greater than p/q.
        # If so, we will return false.
        curr_sum = pre[i - 1] + candidate
        if (A[i] * q > p * curr_sum) :
            flag = False
            break
         
        # comparing like A[i]/(curr_sum)>p/q
        # will be error prone.
     
    return flag
 
  
def solve(n, A, p, q) :
  
    # declaring and constructing
    # prefix sum array
    pre = [0] * 100
    pre[0] = A[0]
    for i in range(1, n) :
        pre[i] = A[i] + pre[i - 1]
     
  
    # setting lower and upper bound for
    # binary search
    lo = 0
    hi = sys.maxsize
    ans = sys.maxsize
  
    # since minimum answer is needed,
    # so it is initialized with INT_MAX
    while (lo <= hi) :
  
        # calculating mid by using (lo+hi)/2
        # may overflow in certain cases
        mid = lo + (hi - lo) // 2
  
        # checking if required ratio would be
        # achieved by all elements if "mid" is
        # considered as answer
        if (isValid(mid, pre, n, A, p, q)) :
            ans = mid
            hi = mid - 1
         
        else :
            lo = mid + 1
         
    return ans
  
# Driver Function
n = 4
p = 1
q = 100
A = [ 20100, 1, 202, 202 ]
  
# printing the required answer
print(solve(n, A, p, q))
 
# This code is contributed by code_hunt.

C#

// C# program for find minimum
// sum of changes in an array
using System;
class GFG
{
 
  // function to check if the candidate sum
  // satisfies the condition of the problem
  static bool isValid(int candidate, int []pre, int n, int []A,
                      int p, int q)
  {
 
    // flag variable to check wrong answer
    bool flag = true;
    for (int i = 1; i < n; i++) {
 
      // Now for each element, we are checking
      // if its ratio with sum of all previous
      // elements + candidate is greater than p/q.
      // If so, we will return false.
      int curr_sum = pre[i - 1] + candidate;
      if (A[i] * q > p * curr_sum) {
        flag = false;
        break;
      }
      // comparing like A[i]/(curr_sum)>p/q
      // will be error prone.
    }
    return flag;
  }
 
  static int solve(int n, int []A, int p, int q)
  {
 
    // declaring and constructing
    // prefix sum array
    int []pre = new int[n];
    pre[0] = A[0];
    for (int i = 1; i < n; i++) {
      pre[i] = A[i] + pre[i - 1];
    }
 
    // setting lower and upper bound for
    // binary search
    int lo = 0, hi = Int32.MaxValue, ans = Int32.MaxValue;
 
    // since minimum answer is needed,
    // so it is initialized with INT_MAX
    while (lo <= hi) {
 
      // calculating mid by using (lo+hi)/2
      // may overflow in certain cases
      int mid = lo + (hi - lo) / 2;
 
      // checking if required ratio would be
      // achieved by all elements if "mid" is
      // considered as answer
      if (isValid(mid, pre, n, A, p, q)) {
        ans = mid;
        hi = mid - 1;
      }
      else {
        lo = mid + 1;
      }
    }
    return ans;
  }
 
  // Driver Function
  public static void Main()
  {
    int n = 4, p = 1, q = 100;
    int []A = { 20100, 1, 202, 202 };
 
    // printing the required answer
    Console.WriteLine(solve(n, A, p, q));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript  program for find minimum
    // sum of changes in an array
    const INT_MAX = 2147483647;
 
    // function to check if the candidate sum
    // satisfies the condition of the problem
    const isValid = (candidate, pre, n, A, p, q) => {
     
        // flag variable to check wrong answer
        let flag = true;
        for (let i = 1; i < n; i++) {
 
            // Now for each element, we are checking
            // if its ratio with sum of all previous
            // elements + candidate is greater than p/q.
            // If so, we will return false.
            let curr_sum = pre[i - 1] + candidate;
            if (A[i] * q > p * curr_sum) {
                flag = false;
                break;
            }
             
            // comparing like A[i]/(curr_sum)>p/q
            // will be error prone.
        }
        return flag;
    }
 
    let solve = (n, A, p, q) => {
 
        // declaring and constructing
        // prefix sum array
        let pre = new Array(n).fill(0);
        pre[0] = A[0];
        for (let i = 1; i < n; i++) {
            pre[i] = A[i] + pre[i - 1];
        }
 
        // setting lower and upper bound for
        // binary search
        let lo = 0, hi = INT_MAX, ans = INT_MAX;
 
        // since minimum answer is needed,
        // so it is initialized with INT_MAX
        while (lo <= hi) {
 
            // calculating mid by using (lo+hi)/2
            // may overflow in certain cases
            let mid = lo + parseInt((hi - lo) / 2);
 
            // checking if required ratio would be
            // achieved by all elements if "mid" is
            // considered as answer
            if (isValid(mid, pre, n, A, p, q)) {
                ans = mid;
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
        return ans;
    }
 
    // Driver Function
    let n, p, q;
    n = 4, p = 1, q = 100;
    let A = [20100, 1, 202, 202];
 
    // printing the required answer
    document.write(solve(n, A, p, q));
 
// This code is contributed by rakeshsahni
 
</script>
Producción

99

Complejidad de tiempo : O(n log(INT_MAX))
Espacio auxiliar : O(n)

Publicación traducida automáticamente

Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *