Buy in minimal price – GeeksforGeeks

An individual has an inventory of N gadgets 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 record whose price is no 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 gadgets from the record, 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
Rationalization: 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 gadgets 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

Method: To resolve the issue observe the beneath observations:

This drawback could be solved utilizing grasping method. Right here the grasping technique as follows.

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

Hereafter, the answer obtained by making use of this technique known as the optimum answer .

There are two potential circumstances 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 circumstances, It’s proven that it doesn’t damage to interchange the optimum answer. Within the following, the coupon with the biggest low cost value doesn’t obey the grasping technique, and all different coupons obey the grasping technique. First, think about the previous case. Then, within the optimum answer c₀ The product that was supposed to make use of m, or for greater priced gadgets, the coupons truly used are listed in descending order of the value of the used merchandise. c₁​,c₂​,…,c_ok​will do.

At this level, the next could be stated.

• mTo c₁​ If shouldn’t be 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 use it for the subsequent most cost-effective merchandise as an alternative. Nonetheless, on this case,c_ok ​can not be utilized to any product. however, c₀ ​The discounted value of c_ok​Since it’s bigger than the discounted value of , there isn’t any total loss. Subsequent, think about the latter case. Then, within the optimum answer c₀. ​The product that was supposed to make use of m₀​, the product truly 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₀ ​ought to 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 any 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 method can also be excessive, m₀ ​The coupon used for m₁ ​can be used for Due to this fact, this trade is at all times 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 monitor 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 aspect of array P into the multiset ms.
  • Additionally, add every aspect 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 aspect of p[i] as D[i] and the second aspect as L[I].
  • This creates pairs of components the place the primary aspect represents the down worth and the second aspect represents the decrease worth.
• Sorting the vector of pairs:
  • Type the vector of pairs p in descending order. The sorting relies on the primary aspect of every pair (D[i]).
  • Sorting in descending order ensures that greater down values are thought-about first.
• Essential logic:
  • Iterate from 0 to M-1.
  • Get the down worth and the decrease worth from the present pair in p.
  • Discover the primary aspect in ms that isn’t 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 aspect is discovered, proceed to the subsequent iteration.
• Output:
  • After the loop ends, print the worth of ans.

Beneath is the implementation for the above method:

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

Final Up to date :
31 Jul, 2023

Like Article