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 checklist 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 complete price required to buy all N gadgets from the checklist, contemplating the obtainable 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 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 unravel the issue comply with the beneath observations:

This drawback may 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 is known as the optimum resolution .

There are two doable instances of non-optimal options:

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

For these two instances, It’s proven that it doesn’t damage to switch the optimum resolution. 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, take into account the previous case. Then, within the optimum resolution c₀ The product that was supposed to make use of m, or for larger priced gadgets, the coupons truly used are listed in descending order of the worth of the used merchandise. c₁​,c₂​,…,c_ok​will do.

At this level, the next may be mentioned.

• mTo c₁​ If shouldn’t be used: mTo c₁ ​Through the use of , it’s doable 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 least expensive merchandise as a substitute. Nevertheless, on this case,c_ok ​can now 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 a general loss. Subsequent, take into account the latter case. Then, within the optimum resolution c₀. ​The product that was supposed to make use of m₀​, the product truly used m₁ ​will do. At this level, the next may be mentioned.
• m₀​ If no coupon has been used for: c₀ ​is used, m₁ ​not m₀ ​needs to be modified to Because of this, the utilization standing of the coupon doesn’t change, and the choices for utilizing different coupons aren’t 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 resolution with an optimum resolution.

• m₀ ​If the coupon is used on: m₀ ​and m₁ ​It’s ample to alternate the vacation spot of the coupon for m₁ ​the worth of m₀ ​For the reason that method can also be excessive, m₀ ​The coupon used for m₁ ​can be used for Due to this fact, this alternate is all the time doable and there’s no loss by this alternate.

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 component of array P into the multiset ms.
  • Additionally, add every component of array P to the variable ans.
• Making a vector of pairs:
  • Create a vector of pairs named p with measurement M.
  • For every index, i from 0 to M-1, set the primary component of p[i] as D[i] and the second component as L[I].
  • This creates pairs of components the place the primary component represents the down worth and the second component represents the decrease worth.
• Sorting the vector of pairs:
  • Kind the vector of pairs p in descending order. The sorting is predicated on the primary component of every pair (D[i]).
  • Sorting in descending order ensures that larger down values are thought-about 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 component 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 component 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 House: O(N + M)

Final Up to date :
31 Jul, 2023

Like Article