diff options
author | Jack Sangdahl <[email protected]> | 2024-11-13 22:07:00 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-13 22:07:08 -0700 |
commit | ecc2fcf61ab52d10b402d8d87146c06c53c4c423 (patch) | |
tree | 7db88fd93e87bd70be7e4a1718581f0c818796f3 | |
parent | 6ce80ea59406da5284927cffc5cf770fb1f09bcd (diff) | |
download | leetcode-ecc2fcf61ab52d10b402d8d87146c06c53c4c423.tar.gz leetcode-ecc2fcf61ab52d10b402d8d87146c06c53c4c423.zip |
2064. minimised maximum of products distributed to any store
-rw-r--r-- | mini_maxi_products_distrib.c | 45 | ||||
-rw-r--r-- | mini_maxi_products_distrib.py | 38 |
2 files changed, 83 insertions, 0 deletions
diff --git a/mini_maxi_products_distrib.c b/mini_maxi_products_distrib.c new file mode 100644 index 0000000..7ea4016 --- /dev/null +++ b/mini_maxi_products_distrib.c @@ -0,0 +1,45 @@ +// 2064. Minimized Maximum of Products Distributed to Any Store +#include "leetcode.h" + +/* + * you are given an integer 'n' indicating that there are 'n' specialty retail + * stores. there are 'm' product types of varying amounts, which are given as a + * 0-indexed integer array 'quantities' owhere 'quantities[i]' represents the + * number of products of the i'th product type. you need to distribute all the + * products to the retail stores following these rules: a store can only be + * given at most one product type but can be given any amount of it, and after + * distribution, each store will have been given some number products. let 'x' + * represent the maximum number of products given to any store. you want 'x' to + * be as small as possible. return the minimum possible 'x'. + */ + +int minimizedMaximum(int n, int *quantities, int quantitiesSize) { + long long sum = 0; + int right = 0; + for (int i = 0; i < quantitiesSize; ++i) { + sum += quantities[i]; + if (right < quantities[i]) + right = quantities[i]; + } + if (sum < n) + return 1; + int left = (int)(sum / n), mid = 0, groups = 0; + while (left <= right) { + mid = left + (right - left) / 2; + groups = 0; + for (int i = 0; i < quantitiesSize; i++) + groups += (quantities[i] + mid - 1) / mid; + if (groups <= n) + right = mid - 1; + else + left = mid + 1; + } + return left; +} + +int main() { + int q1[] = {11, 6}, q2[] = {15, 10, 10}, q3[] = {100000}; + printf("%d\n", minimizedMaximum(6, q1, ARRAY_SIZE(q1))); // expect: 3 + printf("%d\n", minimizedMaximum(7, q2, ARRAY_SIZE(q2))); // expect: 5 + printf("%d\n", minimizedMaximum(1, q3, ARRAY_SIZE(q3))); // expect: 100000 +} diff --git a/mini_maxi_products_distrib.py b/mini_maxi_products_distrib.py new file mode 100644 index 0000000..3baae0a --- /dev/null +++ b/mini_maxi_products_distrib.py @@ -0,0 +1,38 @@ +# 2064. Minimized Maximum of Products Distributed to Any Store +from math import ceil + +""" +you are given an integer 'n' indicating that there are 'n' specialty retail +stores. there are 'm' product types of varying amounts, which are given as a +0-indexed integer array 'quantities' owhere 'quantities[i]' represents the +number of products of the i'th product type. you need to distribute all the +products to the retail stores following these rules: a store can only be +given at most one product type but can be given any amount of it, and after +distribution, each store will have been given some number products. let 'x' +represent the maximum number of products given to any store. you want 'x' to +be as small as possible. return the minimum possible 'x'. +""" + + +class Solution(object): + def minimizedMaximum(self, n, quantities): + """ + :type n: int + :type quantities: List[int] + :rtype: int + """ + right, left = 0, max(quantities) + while right + 1 < left: + mid = (right + left) // 2 + if sum(ceil(i / mid) for i in quantities) <= n: + left = mid + else: + right = mid + return left + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimizedMaximum(n=6, quantities=[11, 6])) + print(obj.minimizedMaximum(n=7, quantities=[15, 10, 10])) + print(obj.minimizedMaximum(n=1, quantities=[100000])) |