leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2064-minimized-maximum-of-products-distributed-to-any-store.rs (3880B)

      1/// 2064. Minimized Maximum of Products Distributed to Any Store (Medium)
      2///
      3/// You are given an integer n indicating there are n specialty retail stores.
      4/// There are m product types of varying amounts, which are given as a
      5/// *0-indexed* integer array quantities, where quantities[i] represents the
      6/// number of products of the ith product type.
      7///
      8/// You need to distribute *all products* to the retail stores following these
      9/// rules:
     10///
     11///   * A store can only be given *at most one product type* but can be given
     12///   *any* amount of it.
     13///   * After distribution, each store will have been given some number of
     14///   products (possibly 0). Let x represent the maximum number of products given
     15///   to any store. You want x to be as small as possible, i.e., you want to
     16///   *minimize* the *maximum* number of products that are given to any store.
     17///
     18/// Return the minimum possible x.
     19///
     20/// *Example 1:*
     21///
     22///   *Input:* n = 6, quantities = [11,6]
     23///   *Output:* 3
     24///   *Explanation:* One optimal way is:
     25///   - The 11 products of type 0 are distributed to the first four stores in these
     26///     amounts: 2, 3, 3, 3
     27///   - The 6 products of type 1 are distributed to the other two stores in these
     28///     amounts: 3, 3
     29///   The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) =
     30///   3.
     31///
     32/// *Example 2:*
     33///
     34///   *Input:* n = 7, quantities = [15,10,10]
     35///   *Output:* 5
     36///   *Explanation:* One optimal way is:
     37///   - The 15 products of type 0 are distributed to the first three stores in these
     38///     amounts: 5, 5, 5
     39///   - The 10 products of type 1 are distributed to the next two stores in these
     40///     amounts: 5, 5
     41///   - The 10 products of type 2 are distributed to the last two stores in these
     42///     amounts: 5, 5
     43///   The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5,
     44///   5) = 5.
     45///
     46/// *Example 3:*
     47///
     48///   *Input:* n = 1, quantities = [100000]
     49///   *Output:* 100000
     50///   *Explanation:* The only optimal way is:
     51///   - The 100000 products of type 0 are distributed to the only store.
     52///   The maximum number of products given to any store is max(100000) = 100000.
     53///
     54/// *Constraints:*
     55///
     56///   * m == quantities.length
     57///   * 1 <= m <= n <= 105
     58///   * 1 <= quantities[i] <= 105
     59///
     60use leetcode::*;
     61
     62struct Solution {}
     63
     64impl Solution {
     65    pub fn minimized_maximum(n: i32, quantities: Vec<i32>) -> i32 {
     66        let n = n as i64;
     67        let (mut lo, mut hi) = (1, 100001);
     68        while lo != hi {
     69            let x = (lo + hi) / 2;
     70            let mut nn = 0i64;
     71            for count in quantities.iter() {
     72                nn += (*count as i64 + x - 1) / x;
     73                if nn > n {
     74                    break;
     75                }
     76            }
     77            if nn <= n {
     78                hi = x
     79            } else {
     80                lo = x + 1
     81            }
     82        }
     83        lo as i32
     84    }
     85}
     86
     87pub fn main() {
     88    println!(
     89        "{:?}",
     90        Solution::minimized_maximum(arg_into(1), arg_into(2))
     91    );
     92}
     93
     94#[cfg(test)]
     95mod tests {
     96    use crate::Solution;
     97    use leetcode::vi;
     98
     99    #[test]
    100    fn test() {
    101        assert_eq!(Solution::minimized_maximum(6, vi("[11,6]")), 3);
    102        assert_eq!(Solution::minimized_maximum(7, vi("[15,10,10]")), 5);
    103        assert_eq!(Solution::minimized_maximum(1, vi("[100000]")), 100000);
    104        assert_eq!(
    105            Solution::minimized_maximum(15, vi("[16,24,18,26,18,28,11,8,22,26,21,23]")),
    106            24
    107        );
    108        assert_eq!(
    109            Solution::minimized_maximum(22, vi("[25,11,29,6,24,4,29,18,6,13,25,30]")),
    110            13
    111        );
    112        assert_eq!(
    113            Solution::minimized_maximum(14, vi("[7,8,22,13,26,21,4,5,23,2,2]")),
    114            21
    115        );
    116        assert_eq!(
    117            Solution::minimized_maximum(20, vi("[8,7,13,27,3,2,29,2,17,2,3,13]")),
    118            9
    119        );
    120    }
    121}