LeetCode-in-Java

4014. Minimum Total Price After Applying Discounts

Medium

You are given two integer arrays prices and discounts.

The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.

You may apply discounts subject to the following rules:

If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.

Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: prices = [10,30,21], discounts = [50,60]

Output: 32.50000

Explanation:

The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.

Example 2:

Input: prices = [100,70], discounts = [10,40,50]

Output: 92.00000

Explanation:

The total is 50 + 42 = 92.00000, which is the minimum possible.

Example 3:

Input: prices = [7,3,9], discounts = [100,100]

Output: 3.00000

Explanation:

The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.

Constraints:

Solution

public class Solution {
    public double minPrice(int[] prices, int[] discounts) {
        int[] discount = new int[101];
        for (int dis : discounts) {
            discount[dis]++;
        }
        int maxprice = 0;
        for (int price : prices) {
            if (maxprice < price) {
                maxprice = price;
            }
        }
        int[] price = new int[maxprice + 1];
        for (int p : prices) {
            price[p]++;
        }
        double ans = 0;
        int i = pos(price, maxprice);
        int j = pos(discount, 100);
        while (i > 0) {
            ans += i - (i * j) / 100.0;
            i = pos(price, i);
            j = pos(discount, j);
        }
        return ans;
    }

    private int pos(int[] arr, int p) {
        for (int i = p; i > 0; i--) {
            if (arr[i] > 0) {
                arr[i]--;
                return i;
            }
        }
        return 0;
    }
}