糖果店

一家糖果店销售各种糖果。第 n 个糖果的价格是 price[n] 枚硬币。顾客们得到了一包含 m 张特别优惠券的袋子。第 m 张优惠券可以用来以 discount[m] 枚硬币的折扣购买至少 req[m] 枚硬币价格的糖果。每张优惠券只能使用一次，并且最多可以用在一颗糖果上。如果他们不使用任何优惠券购买糖果，他们将支付该糖果的常规价格。
顾客们请你帮助他们确定购买商店里所有 n 颗糖果所需的最少硬币数量。

示例1：

n=3
m=3
price = [4, 3, 1]
req = [5, 4, 2]
discount = [4, 4, 2]

To use the minimum coins the customers will use the coupons accordingy
- For the 1st candy the customers can use the 2d coupon and buy the candy for 4-4=0 coins.
- For the 2nd candy,they can use the 3rd coupon and buy the candy for 3-2 = 1 coin.
- For the 3d candy, no coupon left can be used and hence the candy will cost its original price which is 1 coin.

Therefore, the customer will but all candies in 0 + 1 + 1 = 2 coins

示例2：

n=4
m=2
price = [2, 8, 3, 7]
req = [8, 7]
discount = [5, 4]

sum = 2 + (8-5) + 3 + (7-4) = 11

代码

代码是错的, 只过了 8/15 test case

import java.util.Arrays;
import java.util.List;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {

    public static long findMinimumCoins(List<Integer> prices, List<Integer> reqs, List<Integer> discounts) {
        // Sort the prices in ascending order
        Collections.sort(prices);

        // Create a coupon queue prioritized by requirement ascending and then by larger discount for same requirement
        PriorityQueue<int[]> couponQueue = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return Integer.compare(a[0], b[0]); // Smaller requirement first
                }
                return -Integer.compare(a[1], b[1]); // Larger discount for the same requirement
            }
        });

        for (int i = 0; i < reqs.size(); i++) {
            couponQueue.offer(new int[]{reqs.get(i), discounts.get(i)});
        }

        long totalCost = 0;
        // Process each price and attempt to use the best matching coupon
        for (int price : prices) {
            if (!couponQueue.isEmpty()) {
                int[] bestMatch = null;
                // Look for the best applicable coupon
                for (int[] coupon : couponQueue) {
                    if (coupon[0] <= price) {
                        if (bestMatch == null || (coupon[0] == price && coupon[1] > bestMatch[1])) {
                            bestMatch = coupon;
                        }
                    }
                }
                if (bestMatch != null) {
                    totalCost += Math.max(0, price - bestMatch[1]);
                    couponQueue.remove(bestMatch); // Remove the used coupon
                    continue;
                }
            }
            // If no applicable coupon, pay the full price
            totalCost += price;
        }

        return totalCost;
    }

    public static void main(String[] args) {
        // Example price list
        List<Integer> prices = Arrays.asList(2, 8, 3, 7);
        // Requirements for each coupon
        List<Integer> reqs = Arrays.asList(8, 7);
        // Discounts provided by each coupon
        List<Integer> discounts = Arrays.asList(5, 4);

        // Calculating the minimum coins needed
        long minimumCoins = findMinimumCoins(prices, reqs, discounts);

        // Output the result
        System.out.println("Minimum coins required: " + minimumCoins);  // Expected output: 11
    }
}