Mdr-C-Tutorial

主题

10307：抽屉负载的上下界 ​

题目 ​

把 n 个物品放入 m 个抽屉，其中 m > 0、n > 2m。求：

  1. 物品最少的抽屉最多能有多少个物品；
  2. 物品最多的抽屉最少要有多少个物品。

解析 ​

所有抽屉的平均物品数是 n / m。若要让最少的抽屉尽量多，应尽可能均匀分配，其最大值为 ⌊n/m⌋。若要让最多的抽屉尽量少，同样应均匀分配，其最小值为 ⌈n/m⌉。

解析 ​

c
#include <stddef.h>
#include <stdio.h>

int main(void) {
    size_t m;
    size_t n;

    if (scanf("%zu%zu", &m, &n) != 2 || m == 0) {
        return 1;
    }

    size_t largest_minimum = n / m;
    size_t smallest_maximum = n / m + (n % m != 0);

    printf("%zu\n", largest_minimum);
    printf("%zu\n", smallest_maximum);
    return 0;
}

用 n / m + (n % m != 0) 计算向上取整，不需要先计算可能溢出的 n + m - 1。