Dados dos enteros W y C , que representan la cantidad de sandías y monedas, la tarea es encontrar la cantidad máxima de mangos que se pueden comprar dado que cada mango cuesta 1 sandía y se pueden ganar X monedas e y monedas vendiendo una sandía.
Ejemplos:
Entrada: W = 10, C = 10, X = 1, Y = 1
Salida: 10
Explicación: La forma más óptima es usar 10 sandías y 10 monedas para comprar 10 mangos. Por lo tanto, el número máximo de mangos que se pueden comprar es 10.Entrada: W = 4, C = 8, X = 4, Y = 4
Salida: 3
Explicación: La forma más óptima es vender una sandía. Luego, el número de monedas aumenta en 4. Por lo tanto, el número total de monedas se convierte en 12. Por lo tanto, se pueden usar 3 sandías y 12 monedas para comprar 3 mangos. Por lo tanto, el número máximo de mangos que se pueden comprar es 3.
Enfoque: este problema se puede resolver mediante la búsqueda binaria . La idea es encontrar el número máximo de mangos en el espacio de búsqueda. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable ans como 0 para almacenar el resultado requerido.
- Inicialice dos variables l como 0 , r como W para almacenar las regiones límite del espacio de búsqueda para la búsqueda binaria .
- Bucle while l≤r y realice los siguientes pasos:
- Almacene el valor medio en una variable mid como (l+r)/2 .
- Comprueba si se puede comprar una cantidad media de mangos usando el valor dado de W , C , x e y .
- Si es cierto, actualice ans a mid y busque en la parte derecha de mid actualizando l a mid+1 . De lo contrario, actualice el valor de r a mid-1 .
- Imprime el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if mid number
// of mangoes can be bought
bool check(int n, int m, int x, int y, int vl)
{
// Store the coins
int temp = m;
// If watermelons needed are greater
// than given watermelons
if (vl > n)
return false;
// Store remaining watermelons if vl
// watermelons are used to buy mangoes
int ex = n - vl;
// Store the value of coins if these
// watermelon get sold
ex *= y;
// Increment coins by ex
temp += ex;
// Number of mangoes that can be buyed
// if only x coins needed for one mango
int cr = temp / x;
// If the condition is satisfied,
// return true
if (cr >= vl)
return true;
// Otherwise return false
return false;
}
// Function to find the maximum number of mangoes
// that can be bought by selling watermelons
int maximizeMangoes(int n, int m, int x, int y)
{
// Initialize the boundary values
int l = 0, r = n;
// Store the required result
int ans = 0;
// Binary Search
while (l <= r) {
// Store the mid value
int mid = l + (r - l) / 2;
// Check if it is possible to
// buy mid number of mangoes
if (check(n, m, x, y, mid)) {
ans = mid;
l = mid + 1;
}
// Otherwise, update r to mid -1
else
r = mid - 1;
}
// Return the result
return ans;
}
// Driver Code
int main()
{
// Given Input
int W = 4, C = 8, x = 4, y = 4;
// Function Call
cout << maximizeMangoes(W, C, x, y);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if mid number
// of mangoes can be bought
static boolean check(int n, int m, int x,
int y, int vl)
{
// Store the coins
int temp = m;
// If watermelons needed are greater
// than given watermelons
if (vl > n)
return false;
// Store remaining watermelons if vl
// watermelons are used to buy mangoes
int ex = n - vl;
// Store the value of coins if these
// watermelon get sold
ex *= y;
// Increment coins by ex
temp += ex;
// Number of mangoes that can be buyed
// if only x coins needed for one mango
int cr = temp / x;
// If the condition is satisfied,
// return true
if (cr >= vl)
return true;
// Otherwise return false
return false;
}
// Function to find the maximum number
// of mangoes that can be bought by
// selling watermelons
static int maximizeMangoes(int n, int m,
int x, int y)
{
// Initialize the boundary values
int l = 0, r = n;
// Store the required result
int ans = 0;
// Binary Search
while (l <= r)
{
// Store the mid value
int mid = l + (r - l) / 2;
// Check if it is possible to
// buy mid number of mangoes
if (check(n, m, x, y, mid))
{
ans = mid;
l = mid + 1;
}
// Otherwise, update r to mid -1
else
r = mid - 1;
}
// Return the result
return ans;
}
// Driver code
public static void main(String[] args)
{
// Given Input
int W = 4, C = 8, x = 4, y = 4;
// Function Call
System.out.println(maximizeMangoes(W, C, x, y));
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to check if mid number # of mangoes can be bought def check(n, m, x, y, vl): # Store the coins temp = m # If watermelons needed are greater # than given watermelons if (vl > n): return False # Store remaining watermelons if vl # watermelons are used to buy mangoes ex = n - vl # Store the value of coins if these # watermelon get sold ex *= y # Increment coins by ex temp += ex # Number of mangoes that can be buyed # if only x coins needed for one mango cr = temp // x # If the condition is satisfied, # return true if (cr >= vl): return True # Otherwise return false return False # Function to find the maximum number of mangoes # that can be bought by selling watermelons def maximizeMangoes(n, m, x, y): # Initialize the boundary values l = 0 r = n # Store the required result ans = 0 # Binary Search while (l <= r): # Store the mid value mid = l + (r - l) // 2 # Check if it is possible to # buy mid number of mangoes if (check(n, m, x, y, mid)): ans = mid l = mid + 1 # Otherwise, update r to mid -1 else: r = mid - 1 # Return the result return ans # Driver Code if __name__ == '__main__': # Given Input W = 4 C = 8 x = 4 y = 4 # Function Call print(maximizeMangoes(W, C, x, y)) # This code is contributed by bgangwar59
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if mid number
// of mangoes can be bought
static bool check(int n, int m, int x,
int y, int vl)
{
// Store the coins
int temp = m;
// If watermelons needed are greater
// than given watermelons
if (vl > n)
return false;
// Store remaining watermelons if vl
// watermelons are used to buy mangoes
int ex = n - vl;
// Store the value of coins if these
// watermelon get sold
ex *= y;
// Increment coins by ex
temp += ex;
// Number of mangoes that can be buyed
// if only x coins needed for one mango
int cr = temp / x;
// If the condition is satisfied,
// return true
if (cr >= vl)
return true;
// Otherwise return false
return false;
}
// Function to find the maximum number of mangoes
// that can be bought by selling watermelons
static int maximizeMangoes(int n, int m, int x, int y)
{
// Initialize the boundary values
int l = 0, r = n;
// Store the required result
int ans = 0;
// Binary Search
while (l <= r)
{
// Store the mid value
int mid = l + (r - l) / 2;
// Check if it is possible to
// buy mid number of mangoes
if (check(n, m, x, y, mid))
{
ans = mid;
l = mid + 1;
}
// Otherwise, update r to mid -1
else
r = mid - 1;
}
// Return the result
return ans;
}
// Driver Code
public static void Main()
{
// Given Input
int W = 4, C = 8, x = 4, y = 4;
// Function Call
Console.Write(maximizeMangoes(W, C, x, y));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to check if mid number
// of mangoes can be bought
function check(n, m, x, y,vl)
{
// Store the coins
var temp = m;
// If watermelons needed are greater
// than given watermelons
if (vl > n)
return false;
// Store remaining watermelons if vl
// watermelons are used to buy mangoes
var ex = n - vl;
// Store the value of coins if these
// watermelon get sold
ex *= y;
// Increment coins by ex
temp += ex;
// Number of mangoes that can be buyed
// if only x coins needed for one mango
var cr = parseInt(temp / x);
// If the condition is satisfied,
// return true
if (cr >= vl)
return true;
// Otherwise return false
return false;
}
// Function to find the maximum number of mangoes
// that can be bought by selling watermelons
function maximizeMangoes(n, m, x, y)
{
// Initialize the boundary values
var l = 0, r = n;
// Store the required result
var ans = 0;
// Binary Search
while (l <= r) {
// Store the mid value
var mid = l + parseInt((r - l) / 2);
// Check if it is possible to
// buy mid number of mangoes
if (check(n, m, x, y, mid)) {
ans = mid;
l = mid + 1;
}
// Otherwise, update r to mid -1
else
r = mid - 1;
}
// Return the result
return ans;
}
var W = 4, C = 8, x = 4, y = 4;
// Function Call
document.write( maximizeMangoes(W, C, x, y));
//This code is contributed by SoumikMondal
</script>
Producción:
3
Complejidad de tiempo: O(log(W))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sarthakpal5101 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA