Buy in minimal price – GeeksforGeeks

An individual has a listing of N objects to purchase. The price of the i^th merchandise is represented by P_i. He additionally has M coupons. Every coupon can be utilized to buy an merchandise from the listing whose price is not less than L_i, with a reduction of D_i. Every coupon can solely be used as soon as, and a number of coupons can’t be used for a similar merchandise. Discover the minimal whole price required to buy all N objects from the listing, contemplating the out there coupons.

Examples:

Enter: N = 3, M = 3, P[3] = {4, 3, 1}, L[3] = {4, 4, 2}, D[3] = {2, 3, 1}
Output: 4
Clarification: Think about using the 2nd coupon for the 1st merchandise, and the third coupon for the 2nd merchandise. Then, he buys the 1st merchandise for 4-3 = 1, the 2nd merchandise for 3-1 = 2, and the third merchandise for 1. Thus, he should purchase all of the objects for 1 + 2 + 1 = 4

Enter: 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

Strategy: To unravel the issue comply with the under observations:

This drawback could be solved utilizing grasping strategy. Right here the grasping methodology as follows.

• Coupons are checked out in descending order of low cost worth. If there are merchandise for which coupons can be utilized, the coupon is used for the most cost effective product amongst them.

Hereafter, the answer obtained by making use of this methodology is named the optimum answer .

There are two potential instances of non-optimal options:

• He didn’t use a coupon that ought to have been out there.
• He used a coupon that ought to have been out there, however he used the coupon on a non-cheapest merchandise.

For these two instances, It’s proven that it doesn’t harm to exchange the optimum answer. Within the following, the coupon with the biggest low cost worth doesn’t obey the grasping methodology, and all different coupons obey the grasping methodology. First, contemplate the previous case. Then, within the optimum answer c₀ The product that was supposed to make use of m, or for increased priced objects, the coupons really used are listed in descending order of the value of the used merchandise. c₁​,c₂​,…,c_okay​will do.

At this level, the next could be stated.

• mTo c₁​ If isn’t used: mTo c₁ ​By utilizing , it’s potential to extend the variety of coupons that can be utilized whereas sustaining the utilization standing of different coupons.
• m to c₁ ​is used: m to c₁ ​not, c₀ ​use . By doing this, c₁ ​enamel m You should utilize it for the following most cost-effective merchandise as a substitute. Nevertheless, on this case,c_okay ​can not be utilized to any product. however, c₀ ​The discounted worth of c_okay​Since it’s bigger than the discounted worth of , there isn’t a general loss. Subsequent, contemplate the latter case. Then, within the optimum answer c₀. ​The product that was supposed to make use of m₀​, the product really used m₁ ​will do. At this level, the next could be stated.
• m₀​ If no coupon has been used for: c₀ ​is used, m₁ ​not m₀ ​must be modified to Consequently, the utilization standing of the coupon doesn’t change, and the choices for utilizing different coupons should not narrowed.

From the above, it was proven that in each the previous case and the latter case, there isn’t a loss by changing a non-optimal answer with an optimum answer.

• m₀ ​If the coupon is used on: m₀ ​and m₁ ​It’s ample to trade the vacation spot of the coupon for m₁ ​the value of m₀ ​Because the strategy can also be excessive, m₀ ​The coupon used for m₁ ​can be used for Due to this fact, this trade is all the time potential and there’s no loss by this trade.

Beneath are the steps concerned within the implementation of the code:

• Initialization:
  • Initialize a variable ans to maintain observe of the reply.
  • Create a multiset named ms to retailer the weather of array P.
• Inserting components and calculating the preliminary sum:
  • Iterate from 0 to N-1 and insert every factor of array P into the multiset ms.
  • Additionally, add every factor of array P to the variable ans.
• Making a vector of pairs:
  • Create a vector of pairs named p with dimension M.
  • For every index, i from 0 to M-1, set the primary factor of p[i] as D[i] and the second factor as L[I].
  • This creates pairs of components the place the primary factor represents the down worth and the second factor represents the decrease worth.
• Sorting the vector of pairs:
  • Kind the vector of pairs p in descending order. The sorting relies on the primary factor of every pair (D[i]).
  • Sorting in descending order ensures that increased down values are thought of first.
• Primary logic:
  • Iterate from 0 to M-1.
  • Get the down worth and the decrease worth from the present pair in p.
  • Discover the primary factor in ms that’s not lower than the decrease worth utilizing the lower_bound perform.
  • If such a component exists, take away it from ms and subtract the down worth from the variable ans.
  • If no factor is discovered, proceed to the following iteration.
• Output:
  • After the loop ends, print the worth of ans.

Beneath is the implementation for the above strategy:

Time Complexity: O(NlogN + MlogM)
Auxiliary Area: O(N + M)

Final Up to date :
31 Jul, 2023

Like Article