Get Minimum Cost - rFronteddu/general_wiki GitHub Wiki

• There are n items, each associated with two positive values a[i] and b[i].
• There are infinitely many items of each type numbered from 1 to infinity and the item numbered j of type i costs a[i] + (j - 1) * b[i] units.

Determine the minimum possible cost to purchase exactly m items.

public long getMinimumCost (int[] a, int[] b, int m)

• int a[n]: an array of integers
• int b[n]: an array of integers
• m: the number of items to purchase

Returns

• long integer: the minimum cost

To minimize the cost:

1. The cost of items of a given type increases as more items are purchased from that type. Therefore, it's more beneficial to start purchasing cheaper items first and increase gradually.
2. Greedy Strategy:

• We should always try to pick the cheapest available item at any given moment.
• To achieve this, for each type of item, the cost for each subsequent item of that type increases due to the linear formula involving b[i].

3. Using a Min-Heap: We can use a priority queue (or min-heap) to efficiently track and retrieve the next cheapest item available for purchase across all item types.

Steps:

• Initialize a min-heap where each entry contains the cost of the first item of every type (i.e., a[i]).
• Each time an item is selected, push the next item from the same type into the heap. The next item’s cost will be a[i] + b[i].
• Repeat this until exactly m items have been selected.

import java.util.PriorityQueue;

class Item {
    long cost;
    int type;  // The index of the type
    int count; // Which item of this type (1st, 2nd, 3rd, etc.)

    public Item (long cost, int type, int count) {
        this.cost = cost;
        this.type = type;
        this.count = count;
    }
}

public class Solution {
    public long getMinimumCost (int[] a, int[] b, int m) {
        int n = a.length;

        PriorityQueue<Item> pq = new PriorityQueue<>((x, y) -> Long.compare (x.cost, y.cost));
        // Initialize the heap with the first item of each type
        for (int i = 0; i < n; i++) {
            // 1st item of type i
            pq.offer (new Item (a[i], i, 1));  
        }

        long totalCost = 0;

        // We need to purchase exactly m items
        for (int i = 0; i < m; i++) {
            // Get the cheapest item available
            Item cheapest = pq.poll();
            totalCost += cheapest.cost;

            // Add the next item from the same type to the heap
            int type = cheapest.type;
            int nextCount = cheapest.count + 1;
            long nextCost = a[type] + (nextCount - 1L) * b[type];
            pq.offer (new Item (nextCost, type, nextCount));
        }

        return totalCost;
    }
}