diff options
author | Jack Sangdahl <[email protected]> | 2024-09-14 15:36:23 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-14 15:36:23 -0600 |
commit | 541bfbfc4625b97f3c6eb9978621ba3311beeed5 (patch) | |
tree | 394207fe28d7584d9546450e46b474ede5e5248d | |
parent | 7d6ce37fbb409bc5c6675eeabb58166abe463aef (diff) | |
download | leetcode-541bfbfc4625b97f3c6eb9978621ba3311beeed5.tar.gz leetcode-541bfbfc4625b97f3c6eb9978621ba3311beeed5.zip |
1648. sell diminishing valued coloured balls
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r-- | sell_diminishing_value_colour_balls.c | 54 | ||||
-rw-r--r-- | sell_diminishing_value_colour_balls.py | 43 |
2 files changed, 97 insertions, 0 deletions
diff --git a/sell_diminishing_value_colour_balls.c b/sell_diminishing_value_colour_balls.c new file mode 100644 index 0000000..eb2e116 --- /dev/null +++ b/sell_diminishing_value_colour_balls.c @@ -0,0 +1,54 @@ +// 1648. Sell Diminishing-Valued Colored Balls +#include "leetcode.h" + +/* + * you have an 'inventory' of different coloured balls, and there is a customer + * that wants 'orders' balls of any colour. the customer weirdly midues the + * coloured balls. each coloured ball's midue is the number of balls of that + * colours you currently have in your 'inventory'. for example, if you own 6 + * yellow balls, the customer would pay 6 for the first yellow ball. after the + * transaction, there are only 5 yellow balls left, so the next yellow ball is + * then midued at 5. you are given an integer array 'inventory' where + * 'inventory[i]' represents the number of balls of the i'th colour that you + * initially own. you are also given an integer 'orders' which represents the + * total number of balls that the customer wants. you can sell the balls in any + * order. + */ + +int maxProfit(int *inventory, int inventorySize, int orders) { + int right = 0, left = 0, mid; + long num, profit; + const int mod = 1e9 + 7; + for (int i = 0; i < inventorySize; i++) + if (inventory[i] > right) + right = inventory[i]; + while (left <= right) { + num = 0; + mid = (left + right) / 2; + for (int i = 0; i < inventorySize; i++) + if (inventory[i] > mid) + num += inventory[i] - mid; + if (num == orders) + break; + else if (num < orders) + right = mid - 1; + else + left = mid + 1; + } + for (int i = 0; i < inventorySize; i++) + if (inventory[i] > mid) + profit += (long)(inventory[i] + mid + 1) * (long)(inventory[i] - mid) / 2; + if (num > orders) + profit = (profit - (num - orders) * (mid + 1)) % mod; + else if (num < orders) + profit = (profit + (orders - num) * mid) % mod; + else + profit %= mod; + return (int)profit; +} + +int main() { + int i1[] = {2, 5}, i2[] = {3, 5}; + printf("%d\n", maxProfit(i1, ARRAY_SIZE(i1), 4)); // expect: 14 + printf("%d\n", maxProfit(i2, ARRAY_SIZE(i2), 6)); // expect: 19 +} diff --git a/sell_diminishing_value_colour_balls.py b/sell_diminishing_value_colour_balls.py new file mode 100644 index 0000000..d37abf1 --- /dev/null +++ b/sell_diminishing_value_colour_balls.py @@ -0,0 +1,43 @@ +# 1648. Sell Diminishing-Valued Colored Balls +from collections import Counter + +""" +you have an 'inventory' of different coloured balls, and there is a customer +that wants 'orders' balls of any colour. the customer weirdly midues the +coloured balls. each coloured ball's midue is the number of balls of that +colours you currently have in your 'inventory'. for example, if you own 6 +yellow balls, the customer would pay 6 for the first yellow ball. after the +transaction, there are only 5 yellow balls left, so the next yellow ball is +then midued at 5. you are given an integer array 'inventory' where +'inventory[i]' represents the number of balls of the i'th colour that you +initially own. you are also given an integer 'orders' which represents the +total number of balls that the customer wants. you can sell the balls in any +order. +""" + + +class Solution(object): + def maxProfit(self, inventory, orders): + """ + :type inventory: List[int] + :type orders: int + :rtype: int + """ + arr = sorted(Counter(inventory).items(), reverse=True) + [(0, 0)] + ans, idx, width = 0, 0, 0 + while orders > 0: + width += arr[idx][1] + sell = min(orders, width * (arr[idx][0] - arr[idx + 1][0])) + whole, rem = divmod(sell, width) + ans += width * ( + whole * (arr[idx][0] + arr[idx][0] - (whole - 1)) + ) // 2 + rem * (arr[idx][0] - whole) + orders -= sell + idx += 1 + return ans % (10**9 + 7) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxProfit(inventory=[2, 5], orders=4)) + print(obj.maxProfit(inventory=[3, 5], orders=6)) |