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 (3733B)

      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///
     60
     61use leetcode::*;
     62
     63struct Solution {}
     64
     65impl Solution {
     66    pub fn minimized_maximum(n: i32, quantities: Vec<i32>) -> i32 {
     67        let n = n as i64;
     68        let (mut lo, mut hi) = (1, 100001);
     69        while lo != hi {
     70            let x = (lo + hi) / 2;
     71            let mut nn = 0i64;
     72            for count in quantities.iter() {
     73                nn += (*count as i64 + x - 1) / x;
     74                if nn > n {
     75                    break;
     76                }
     77            }
     78            if nn <= n {
     79                hi = x
     80            } else {
     81                lo = x + 1
     82            }
     83        }
     84        lo as i32
     85    }
     86}
     87
     88pub fn main() {
     89    println!("{:?}", Solution::minimized_maximum(arg_into(1), arg_into(2)));
     90}
     91
     92#[cfg(test)]
     93mod tests {
     94    use crate::Solution;
     95
     96    #[test]
     97    fn test() {
     98        assert_eq!(Solution::minimized_maximum(6, vec![11, 6]), 3);
     99        assert_eq!(Solution::minimized_maximum(7, vec![15, 10, 10]), 5);
    100        assert_eq!(Solution::minimized_maximum(1, vec![100000]), 100000);
    101        assert_eq!(Solution::minimized_maximum(15, vec![16, 24, 18, 26, 18, 28, 11, 8, 22, 26, 21, 23]), 24);
    102        assert_eq!(Solution::minimized_maximum(22, vec![25, 11, 29, 6, 24, 4, 29, 18, 6, 13, 25, 30]), 13);
    103        assert_eq!(Solution::minimized_maximum(14, vec![7, 8, 22, 13, 26, 21, 4, 5, 23, 2, 2]), 21);
    104        assert_eq!(Solution::minimized_maximum(20, vec![8, 7, 13, 27, 3, 2, 29, 2, 17, 2, 3, 13]), 9);
    105    }
    106}