aboutsummaryrefslogtreecommitdiff
path: root/mini_maxi_products_distrib.c
blob: 7ea4016270e922da10f126606d0f5541ed3adc0a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
}