En un mercado de valores, hay un producto con sus acciones infinitas. Los precios de las acciones se dan para N días, donde arr[i] denota el precio de las acciones en el i -ésimo día. Existe una regla según la cual un cliente puede comprar como máximo i existencias el i -ésimo día. Si el cliente tiene una cantidad de k cantidad de dinero inicialmente, averigüe la cantidad máxima de acciones que puede comprar un cliente.
Por ejemplo, durante 3 días, el precio de una acción es 7, 10, 4. Puede comprar 1 acción que vale 7 rs el día 1, 2 acciones que valen 10 rs cada una el día 2 y 3 acciones que valen 4 rs cada una el día 3.
Ejemplos:
Input : price[] = { 10, 7, 19 }, k = 45. Output : 4 A customer purchases 1 stock on day 1 for 10 rs, 2 stocks on day 2 for 7 rs each and 1 stock on day 3 for 19 rs.Therefore total of 10, 7 * 2 = 14 and 19 respectively. Hence, total amount is 10 + 14 + 19 = 43 and number of stocks purchased is 4. Input : price[] = { 7, 10, 4 }, k = 100. Output : 6
La idea es utilizar un enfoque codicioso, en el que deberíamos comenzar a comprar productos desde el día en que el precio de las acciones sea menor y así sucesivamente.
Por lo tanto, ordenaremos el par de dos valores, es decir, {precio de las acciones, día} de acuerdo con el precio de las acciones, y si los precios de las acciones son iguales, entonces ordenaremos según el día.
Ahora, recorreremos la lista ordenada de pares y comenzaremos a comprar de la siguiente manera:
Digamos que nos quedan R rs hasta ahora, y el costo del producto en este día es C, y podemos comprar como máximo L productos en este día entonces,
compra total en este día (P) = min(L, R/C)
Ahora, agregue este valor a la respuesta
compra_total = compra_total + P, donde P =min(L, R/C)
Ahora, reste el costo de comprando P artículos con el dinero restante, R = R – P*C.
El número total de productos que podemos comprar es igual a total_purchase.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find maximum number of stocks that // can be bought with given constraints. #include <bits/stdc++.h> using namespace std; // Return the maximum stocks int buyMaximumProducts(int n, int k, int price[]) { vector<pair<int, int> > v; // Making pair of product cost and number // of day.. for (int i = 0; i < n; ++i) v.push_back(make_pair(price[i], i + 1)); // Sorting the vector pair. sort(v.begin(), v.end()); // Calculating the maximum number of stock // count. int ans = 0; for (int i = 0; i < n; ++i) { ans += min(v[i].second, k / v[i].first); k -= v[i].first * min(v[i].second, (k / v[i].first)); } return ans; } // Driven Program int main() { int price[] = { 10, 7, 19 }; int n = sizeof(price)/sizeof(price[0]); int k = 45; cout << buyMaximumProducts(n, k, price) << endl; return 0; }
Java
// Java program to find maximum number of stocks that // can be bought with given constraints. import java.util.*; // Helper class class Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; } } // For Sorting using Pair.first value class SortPair implements Comparator<Pair> { public int compare(Pair a, Pair b) { return a.first - b.first; } } public class GFG { // Return the maximum stocks static int buyMaximumProducts(int[] price, int K, int n) { Pair[] arr = new Pair[n]; // Making pair of product cost and number of day.. for (int i = 0; i < n; i++) arr[i] = new Pair(price[i], i + 1); // Sorting the pair array. Arrays.sort(arr, new SortPair()); // Calculating the maximum number of stock // count. int ans = 0; for (int i = 0; i < n; i++) { ans += Math.min(arr[i].second, K / arr[i].first); K -= arr[i].first * Math.min(arr[i].second, K / arr[i].first); } return ans; } // Driver code public static void main(String[] args) { int[] price = { 10, 7, 19 }; int K = 45; // int []price = { 7, 10, 4 }; // int K = 100; System.out.println( buyMaximumProducts(price, K, price.length)); } } // This code is contributed by Aakash Choudhary
Python3
# Python3 program to find maximum number of stocks # that can be bought with given constraints. # Returns the maximum stocks def buyMaximumProducts(n, k, price): # Making pair of stock cost and day number arr = [] for i in range(n): arr.append([i + 1, price[i]]) # Sort based on the price of stock arr.sort(key = lambda x: x[1]) # Calculating the max stocks purchased total_purchase = 0 for i in range(n): P = min(arr[i][0], k//arr[i][1]) total_purchase += P k -= (P * arr[i][1]) return total_purchase # Driver code price = [ 10, 7, 19 ] n = len(price) k = 45 print(buyMaximumProducts(n, k, price)) # This code is contributed by Tharun Reddy
Producción:
4
Complejidad de tiempo: O (nlogn).
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA