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 = 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 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,…,ckwill 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 ckSince 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
namedms
to store the elements of array P.
- Initialize a variable
- 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
.
- Iterate from 0 to N-1 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 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.
- 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 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 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++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { // Set up the inputs // N is the size of array P, M is the // size of arrays L and D ll N = 3, M = 3; // Array P vector<ll> P = { 4, 3, 1 }; // Array L vector<ll> L = { 4, 4, 2 }; // Array D vector<ll> D = { 2, 3, 1 }; // Variable to store the answer ll ans = 0; // Multiset to store elements of // array P multiset<ll> ms; // Insert elements of array P into // the multiset and calculate // initial sum for (ll i = 0; i < N; i++) { ms.insert(P[i]); ans += P[i]; } // Vector of pairs to store // pairs of D and L values vector<pair<ll, ll> > p(M); // Fill the vector of pairs with // D and L values for (ll i = 0; i < M; i++) { // Set the first element of the // pair as D[i] p[i].first = D[i]; // Set the second element of the // pair as L[i] p[i].second = L[i]; } // Sort the vector of pairs // in descending order based on // the first element (D[i]) sort(p.rbegin(), p.rend()); // Iterate through the pairs and // update the answer for (ll i = 0; i < M; i++) { // Get the down value from the // current pair ll down = p[i].first; // Get the lower value from // the current pair ll lower = p[i].second; // Find the first element in the // multiset that is not less // than the lower value auto itr = ms.lower_bound(lower); // If no element is found, continue // to the next iteration if (itr == ms.end()) { continue ; } // Remove the element from the multiset ms.erase(itr); // Subtract the down value from // the answer ans -= down; } // Output the answer cout << ans << endl; } |
Java
// Java program for the above approach import java.util.*; class Main { public static void main(String[] args) { // Set up the inputs // N is the size of array P, M is the // size of arrays L and D int N = 3 , M = 3 ; // Array P List<Long> P = Arrays.asList(4L, 3L, 1L); // Array L List<Long> L = Arrays.asList(4L, 4L, 2L); // Array D List<Long> D = Arrays.asList(2L, 3L, 1L); // Variable to store the answer long ans = 0 ; // TreeSet to store elements of // array P TreeSet<Long> ts = new TreeSet<>(); // Insert elements of array P into // the TreeSet and calculate // initial sum for ( int i = 0 ; i < N; i++) { ts.add(P.get(i)); ans += P.get(i); } // Array of pairs to store // pairs of D and L values ArrayList<Pair> p = new ArrayList<>(); // Fill the array of pairs with // D and L values for ( int i = 0 ; i < M; i++) { p.add( new Pair(D.get(i), L.get(i))); } // Sort the array of pairs // in descending order based on // the first element (D[i]) Collections.sort(p, new Comparator<Pair>() { @Override public int compare(Pair o1, Pair o2) { return o2.d.compareTo( o1.d); // Compare in reverse order } }); // Iterate through the pairs and // update the answer for ( int i = 0 ; i < M; i++) { // Get the down value from the // current pair long down = p.get(i).d; // Get the lower value from // the current pair long lower = p.get(i).l; // Find the first element in the // TreeSet that is not less // than the lower value Long val = ts.ceiling(lower); // If no element is found, continue // to the next iteration if (val == null ) { continue ; } // Remove the element from the TreeSet ts.remove(val); // Subtract the down value from // the answer ans -= down; } // Output the answer System.out.println(ans); } static class Pair { private final Long d; private final Long l; public Pair(Long d, Long l) { this .d = d; this .l = l; } } } // This code is contributed by Abhinav Mahajan // (abhinav_m22). |
Python3
# Set up the inputs # N is the size of array P, M is the # size of arrays L and D N, M = 3 , 3 # Array P P = [ 4 , 3 , 1 ] # Array L L = [ 4 , 4 , 2 ] # Array D D = [ 2 , 3 , 1 ] # Variable to store the answer ans = 0 # List to store elements of array P ms = [] # Insert elements of array P into # the list and calculate initial sum for i in range (N): ms.append(P[i]) ans + = P[i] # List of tuples to store pairs of D and L values p = [] # Fill the list of tuples with D and L values for i in range (M): p.append((D[i], L[i])) # Sort the list of tuples in descending order based on # the first element (D[i]) p.sort(reverse = True ) # Iterate through the tuples and update the answer for i in range (M): # Get the down value from the current tuple down = p[i][ 0 ] # Get the lower value from the current tuple lower = p[i][ 1 ] # Find the first element in the list that is not less # than the lower value found = False for j in range ( len (ms)): if ms[j] > = lower: ms.pop(j) found = True break # If no element is found, continue to the next iteration if not found: continue # Subtract the down value from the answer ans - = down # Output the answer print (ans) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // Set up the inputs // N is the size of array P, M is the // size of arrays L and D int M = 3; // Array P List< long > P = new List< long > { 4, 3, 1 }; // Array L List< long > L = new List< long > { 4, 4, 2 }; // Array D List< long > D = new List< long > { 2, 3, 1 }; // Variable to store the answer long ans = 0; // SortedSet to store elements of // array P in sorted order SortedSet< long > sortedSet = new SortedSet< long >(P); // Insert elements of array P into // the SortedSet and calculate // initial sum foreach ( long val in P) { sortedSet.Add(val); ans += val; } // List of ValueTuple to store // pairs of D and L values List<( long , long )> pairs = new List<( long , long )>(); // Fill the list of ValueTuple with // D and L values for ( int i = 0; i < M; i++) { // Set the first element of the // ValueTuple as D[i] long down = D[i]; // Set the second element of the // ValueTuple as L[i] long lower = L[i]; pairs.Add((down, lower)); } // Sort the list of ValueTuple // in descending order based on // the first element (D[i]) pairs = pairs.OrderByDescending(p => p.Item1).ToList(); // Iterate through the ValueTuples and // update the answer foreach ( var pair in pairs) { // Get the down value from the // current ValueTuple long down = pair.Item1; // Get the lower value from // the current ValueTuple long lower = pair.Item2; // Find the first element in the // SortedSet that is not less // than the lower value var itr = sortedSet.GetViewBetween(lower, long .MaxValue).FirstOrDefault(); // If no element is found, continue // to the next iteration if (itr == 0) { continue ; } // Remove the element from the SortedSet sortedSet.Remove(itr); // Subtract the down value from // the answer ans -= down; } // Output the answer Console.WriteLine(ans); } } |
Javascript
// Define a class for pairs class Pair { constructor(d, l) { this .d = d; this .l = l; } } // Function to calculate the answer function calculateAnswer() { // Set up the inputs // N is the size of array P, M is the // size of arrays L and D const N = 3; const M = 3; // Array P const P = [4, 3, 1]; // Array L const L = [4, 4, 2]; // Array D const D = [2, 3, 1]; // Variable to store the answer let ans = 0; // Set to store elements of array P const ts = new Set(); // Insert elements of array P into // the Set and calculate initial sum for (let i = 0; i < N; i++) { ts.add(P[i]); ans += P[i]; } // Array of pairs to store pairs of D and L values const p = []; // Fill the array of pairs with D and L values for (let i = 0; i < M; i++) { p.push( new Pair(D[i], L[i])); } // Sort the array of pairs in descending order based on // the first element (D[i]) p.sort((o1, o2) => o2.d - o1.d); // Iterate through the pairs and update the answer for (let i = 0; i < M; i++) { // Get the down value from the current pair const down = p[i].d; // Get the lower value from the current pair const lower = p[i].l; // Find the first element in the Set that is not less // than the lower value let val = null ; for (let element of ts) { if (element >= lower) { val = element; break ; } } // If no element is found, continue to the next iteration if (val === null ) { continue ; } // Remove the element from the Set ts. delete (val); // Subtract the down value from the answer ans -= down; } // Output the answer console.log(ans); } // Call the function to calculate the answer calculateAnswer(); |
4
Time Complexity: O(NlogN + MlogM)
Auxiliary Space: O(N + M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!