commit bd300c28ba61b8e9c6c003255a65d4a8e685fdb9
parent f42abd7454ae390e446d6d43c99113706982d0e9
Author: Louis Burda <quent.burda@gmail.com>
Date: Thu, 21 Nov 2024 01:28:18 +0100
Add problem 2064
Diffstat:
2 files changed, 110 insertions(+), 0 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -59,3 +59,7 @@ path = "src/bin/1574-shortest-subarray-to-be-removed-to-make-array-sorted.rs"
name = "386"
path = "src/bin/0386-lexicographical-numbers.rs"
+[[bin]]
+name = "2064"
+path = "src/bin/2064-minimized-maximum-of-products-distributed-to-any-store.rs"
+
diff --git a/src/bin/2064-minimized-maximum-of-products-distributed-to-any-store.rs b/src/bin/2064-minimized-maximum-of-products-distributed-to-any-store.rs
@@ -0,0 +1,106 @@
+/// 2064. Minimized Maximum of Products Distributed to Any Store (Medium)
+///
+/// You are given an integer n indicating there are n specialty retail stores.
+/// There are m product types of varying amounts, which are given as a
+/// *0-indexed* integer array quantities, where quantities[i] represents the
+/// number of products of the ith product type.
+///
+/// You need to distribute *all 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.
+/// * After distribution, each store will have been given some number of
+/// products (possibly 0). Let x represent the maximum number of products given
+/// to any store. You want x to be as small as possible, i.e., you want to
+/// *minimize* the *maximum* number of products that are given to any store.
+///
+/// Return the minimum possible x.
+///
+/// *Example 1:*
+///
+/// *Input:* n = 6, quantities = [11,6]
+/// *Output:* 3
+/// *Explanation:* One optimal way is:
+/// - The 11 products of type 0 are distributed to the first four stores in these
+/// amounts: 2, 3, 3, 3
+/// - The 6 products of type 1 are distributed to the other two stores in these
+/// amounts: 3, 3
+/// The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) =
+/// 3.
+///
+/// *Example 2:*
+///
+/// *Input:* n = 7, quantities = [15,10,10]
+/// *Output:* 5
+/// *Explanation:* One optimal way is:
+/// - The 15 products of type 0 are distributed to the first three stores in these
+/// amounts: 5, 5, 5
+/// - The 10 products of type 1 are distributed to the next two stores in these
+/// amounts: 5, 5
+/// - The 10 products of type 2 are distributed to the last two stores in these
+/// amounts: 5, 5
+/// The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5,
+/// 5) = 5.
+///
+/// *Example 3:*
+///
+/// *Input:* n = 1, quantities = [100000]
+/// *Output:* 100000
+/// *Explanation:* The only optimal way is:
+/// - The 100000 products of type 0 are distributed to the only store.
+/// The maximum number of products given to any store is max(100000) = 100000.
+///
+/// *Constraints:*
+///
+/// * m == quantities.length
+/// * 1 <= m <= n <= 105
+/// * 1 <= quantities[i] <= 105
+///
+
+use leetcode::*;
+
+struct Solution {}
+
+impl Solution {
+ pub fn minimized_maximum(n: i32, quantities: Vec<i32>) -> i32 {
+ let n = n as i64;
+ let (mut lo, mut hi) = (1, 100001);
+ while lo != hi {
+ let x = (lo + hi) / 2;
+ let mut nn = 0i64;
+ for count in quantities.iter() {
+ nn += (*count as i64 + x - 1) / x;
+ if nn > n {
+ break;
+ }
+ }
+ if nn <= n {
+ hi = x
+ } else {
+ lo = x + 1
+ }
+ }
+ lo as i32
+ }
+}
+
+pub fn main() {
+ println!("{:?}", Solution::minimized_maximum(arg_into(1), arg_into(2)));
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::Solution;
+
+ #[test]
+ fn test() {
+ assert_eq!(Solution::minimized_maximum(6, vec![11, 6]), 3);
+ assert_eq!(Solution::minimized_maximum(7, vec![15, 10, 10]), 5);
+ assert_eq!(Solution::minimized_maximum(1, vec![100000]), 100000);
+ assert_eq!(Solution::minimized_maximum(15, vec![16, 24, 18, 26, 18, 28, 11, 8, 22, 26, 21, 23]), 24);
+ assert_eq!(Solution::minimized_maximum(22, vec![25, 11, 29, 6, 24, 4, 29, 18, 6, 13, 25, 30]), 13);
+ assert_eq!(Solution::minimized_maximum(14, vec![7, 8, 22, 13, 26, 21, 4, 5, 23, 2, 2]), 21);
+ assert_eq!(Solution::minimized_maximum(20, vec![8, 7, 13, 27, 3, 2, 29, 2, 17, 2, 3, 13]), 9);
+ }
+}
