2944. Minimum Number of Coins for Fruits

You are at a fruit market with different types of exotic fruits on display.

You are given a 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the ith fruit.

The fruit market has the following offer:

• If you purchase the ith fruit at prices[i] coins, you can get the next i fruits for free.

Note that even if you can take fruit j for free, you can still purchase it for prices[j] coins to receive a new offer.

Return the minimum number of coins needed to acquire all the fruits.

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> free;
        int now = 0, res = INT_MAX;
        for(int i = 0; i < prices.size(); i++) {
            while(free.size() and free.top().second < i) free.pop();
            int best = now;
            if(free.size()) best = min(best, free.top().first);
            int j = i + 2 + i;
            free.push({best + prices[i], j});
            now = best + prices[i];
            if(j >= prices.size()) res = min(res, best + prices[i]);
        }
        res = min(res, now);
        return res;
    }
};