Comprar acciones máximas si las acciones i se pueden comprar en el i-ésimo día

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++ 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 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 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.