Software Development

Purchase in minimal cost – GeeksforGeeks


A person has a list of N items to buy. The cost of the ith item is represented by Pi. He also has M coupons. Each coupon can be used to purchase an item from the list whose cost is at least Li, with a discount of Di. 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 4-3 = 1, the 2nd item for 3-1 = 2, and the 3rd item for 1. Thus, he can buy all the items for 1 + 2 + 1 = 4

Input: 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 non-optimal 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 non-cheapest 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 c0 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. c1​,c2​,…,ck​will do.

At this point, the following can be said.

  • mTo c1​ If is not used: mTo c1 ​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 c1 ​is used: m to c1 ​not, c0 ​use . By doing this, c1 ​teeth m You can use it for the next cheapest item instead. However, in this case,ck ​can no longer be applied to any product. but, c0 ​The discounted price of ck​Since it is larger than the discounted price of , there is no overall loss. Next, consider the latter case. Then, in the optimal solution c0. ​The product that was supposed to use m0​, the product actually used m1 ​will do. At this point, the following can be said.
  • m0​ If no coupon has been used for: c0 ​is used, m1 ​not m0 ​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 non-optimal solution with an optimal solution.

  • m0 ​If the coupon is used on: m0 ​and m1 ​It is sufficient to exchange the destination of the coupon for m1 ​the price of m0 ​Since the approach is also high, m0 ​The coupon used for m1 ​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 named ms to store the elements of array P.
  • Inserting elements and calculating the initial sum:
    • Iterate from 0 to N-1 and insert each element of array P into the multiset ms.
    • Also, add each element of array P to the variable ans.
  • Creating a vector of pairs:
    • Create a vector of pairs named p with size M.
    • For each index, i from 0 to M-1, 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.
  • 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.
  • Main logic:
    • Iterate from 0 to M-1.
    • 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 the lower_bound function.
    • If such an element exists, remove it from ms and subtract the down value from the variable ans.
    • If no element is found, continue to the next iteration.
  • Output:
    • After the loop ends, print the value of ans.

Below is the implementation for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

 

int main()

{

 

    

 

    

    

    ll N = 3, M = 3;

 

    

    vector<ll> P = { 4, 3, 1 };

 

    

    vector<ll> L = { 4, 4, 2 };

 

    

    vector<ll> D = { 2, 3, 1 };

 

    

    ll ans = 0;

 

    

    

    multiset<ll> ms;

 

    

    

    

    for (ll i = 0; i < N; i++) {

        ms.insert(P[i]);

        ans += P[i];

    }

 

    

    

    vector<pair<ll, ll> > p(M);

 

    

    

    for (ll i = 0; i < M; i++) {

 

        

        

        p[i].first = D[i];

 

        

        

        p[i].second = L[i];

    }

 

    

    

    

    sort(p.rbegin(), p.rend());

 

    

    

    for (ll i = 0; i < M; i++) {

 

        

        

        ll down = p[i].first;

 

        

        

        ll lower = p[i].second;

 

        

        

        

        auto itr = ms.lower_bound(lower);

 

        

        

        if (itr == ms.end()) {

            continue;

        }

 

        

        ms.erase(itr);

 

        

        

        ans -= down;

    }

 

    

    cout << ans << endl;

}

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

Last Updated :
31 Jul, 2023

Like Article

Save Article