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:
discounts[1] = 60 to prices[1] = 30, thus 30 * (100 - 60) / 100 = 12.discounts[0] = 50 to prices[2] = 21, thus 21 * (100 - 50) / 100 = 10.5.prices[0] = 10 receives no discount, so it stays 10.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:
discounts[2] = 50 to prices[0] = 100, thus 100 * (100 - 50) / 100 = 50.discounts[1] = 40 to prices[1] = 70, thus 70 * (100 - 40) / 100 = 42.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:
discounts[0] = 100 to prices[2] = 9, thus 9 * (100 - 100) / 100 = 0.discounts[1] = 100 to prices[0] = 7, thus 7 * (100 - 100) / 100 = 0.prices[1] = 3 receives no discount, so it stays 3.The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.
Constraints:
1 <= prices.length, discounts.length <= 1051 <= prices[i] <= 1051 <= discounts[j] <= 100class Solution {
fun minPrice(prices: IntArray, discounts: IntArray): Double {
val discount = IntArray(101)
for (dis in discounts) {
discount[dis]++
}
var maxprice = 0
for (price in prices) {
if (maxprice < price) {
maxprice = price
}
}
val price = IntArray(maxprice + 1)
for (p in prices) {
price[p]++
}
var ans = 0.0
var i = pos(price, maxprice)
var j = pos(discount, 100)
while (i > 0) {
ans += i - (i * j) / 100.0
i = pos(price, i)
j = pos(discount, j)
}
return ans
}
private fun pos(arr: IntArray, p: Int): Int {
for (i in p downTo 1) {
if (arr[i] > 0) {
arr[i]--
return i
}
}
return 0
}
}