Purchase in minimal cost – GeeksforGeeks
A person has a list of N items to buy. The cost of the i^{th} item is represented by P_{i}. He also has M coupons. Each coupon can be used to purchase an item from the list whose cost is at least L_{i}, with a discount of D_{i}. Each coupon can only be used once, and multiple coupons cannot be used for the same item. Find the minimum total cost required to purchase all N items from the list, considering the available coupons.
Examples:
Input: N = 3, M = 3, P[3] = {4, 3, 1}, L[3] = {4, 4, 2}, D[3] = {2, 3, 1}
Output: 4
Explanation: Consider using the 2nd coupon for the 1st item, and the 3rd coupon for the 2nd item. Then, he buys the 1st item for 43 = 1, the 2nd item for 31 = 2, and the 3rd item for 1. Thus, he can buy all the items for 1 + 2 + 1 = 4Input: N = 10, M = 5, P[10] = {9, 7, 1, 5, 2, 2, 5, 5, 7, 6}, L[3] = {7, 2, 7, 8, 2}, D[3] = {3, 2, 4, 1, 2}
Output: 37
Approach: To solve the problem follow the below observations:
This problem can be solved using greedy approach. Here the greedy method as follows.
 Coupons are looked at in descending order of discount price. If there are products for which coupons can be used, the coupon is used for the cheapest product among them.
Hereafter, the solution obtained by applying this method is called the optimal solution .
There are two possible cases of nonoptimal solutions:
 He didn’t use a coupon that should have been available.
 He used a coupon that should have been available, but he used the coupon on a noncheapest item.
For these two cases, It is shown that it does not hurt to replace the optimal solution. In the following, the coupon with the largest discount price does not obey the greedy method, and all other coupons obey the greedy method. First, consider the former case. Then, in the optimal solution c_{0 }The product that was supposed to use m, or for higher priced items, the coupons actually used are listed in descending order of the price of the used item. c_{1},c_{2},…,c_{k}will do.
At this point, the following can be said.
 mTo c_{1} If is not used: mTo c_{1 }By using , it is possible to increase the number of coupons that can be used while maintaining the usage status of other coupons.
 m to c_{1 }is used: m to c_{1 }not, c_{0 }use . By doing this, c_{1 }teeth m You can use it for the next cheapest item instead. However, in this case,c_{k }can no longer be applied to any product. but, c_{0 }The discounted price of c_{k}Since it is larger than the discounted price of , there is no overall loss. Next, consider the latter case. Then, in the optimal solution c_{0}. The product that was supposed to use m_{0}, the product actually used m_{1 }will do. At this point, the following can be said.
 m_{0} If no coupon has been used for: c_{0 }is used, m_{1 }not m_{0 }should be changed to As a result, the usage status of the coupon does not change, and the options for using other coupons are not narrowed.
From the above, it was shown that in both the former case and the latter case, there is no loss by replacing a nonoptimal solution with an optimal solution.
 m_{0 }If the coupon is used on: m_{0 }and m_{1 }It is sufficient to exchange the destination of the coupon for m_{1 }the price of m_{0 }Since the approach is also high, m_{0 }The coupon used for m_{1 }can also be used for Therefore, this exchange is always possible and there is no loss by this exchange.
Below are the steps involved in the implementation of the code:
 Initialization:
 Initialize a variable
ans
to keep track of the answer.  Create a
multiset
namedms
to store the elements of array P.
 Initialize a variable
 Inserting elements and calculating the initial sum:
 Iterate from 0 to N1 and insert each element of array P into the
multiset
ms
.  Also, add each element of array P to the variable
ans
.
 Iterate from 0 to N1 and insert each element of array P into the
 Creating a vector of pairs:
 Create a vector of pairs named
p
with size M.  For each index, i from 0 to M1, set the first element of
p[i]
as D[i] and the second element as L[I].  This creates pairs of elements where the first element represents the down value and the second element represents the lower value.
 Create a vector of pairs named
 Sorting the vector of pairs:
 Sort the vector of pairs
p
in descending order. The sorting is based on the first element of each pair (D[i]).  Sorting in descending order ensures that higher down values are considered first.
 Sort the vector of pairs
 Main logic:
 Iterate from 0 to M1.
 Get the down value and the lower value from the current pair in
p
.  Find the first element in
ms
that is not less than the lower value using thelower_bound
function.  If such an element exists, remove it from
ms
and subtract the down value from the variableans
.  If no element is found, continue to the next iteration.
 Output:
 After the loop ends, print the value of
ans
.
 After the loop ends, print the value of
Below is the implementation for the above approach:
C++

Time Complexity: O(NlogN + MlogM)
Auxiliary Space: O(N + M)
Last Updated :
31 Jul, 2023
Like Article
Save Article