题目内容

现在存在 $m$ 个房间，有 $n$ 个人需要入住，需要列出所有房间入住可以安排的情况。

假设每个房间可以入住的人数限制为 $5$ 人。

限制条件，为了公平起见，不能存在一个房间的人数比别的房间的人数多 $2$ 个。

输出的组合中房间敏感的，即 $1,1,2$ 组合和 $2,1,1$ 组合是不同的组合，都需要输出，$1,1,2$ 组合代表第一个房间住 $1$ 个人，第二个房间住 $1$ 个人，第三个房间 $2$ 个人，而 $2,1,1$ 组合代表第一个房间住 $2$ 个人，第一个房间住 $1$ 个人，第三个房间住 $1$ 个人。

解题思路

题目分析

• 公平约束：由于任意两房间人数差不能达到 2，所以所有房间人数要么相同，要么只差 1。这就意味着每种可行分布只能由两种相邻的整数构成：$\{k, k+1\}$。
• 最大化入住：我们要尽量安排更多人进房以减少剩余，故目标是最大化已安排人数。
• 情况分两类：
  1. 当 $\lfloor n/m\rfloor \ge 5$ 时，每个房间最多可住 5 人，故所有房间都住 5 人，剩余 $n - 5m$。
  2. 否则令
     $k = \left\lfloor \frac{n}{m} \right\rfloor$, $r = n - m\,k,$ 则恰好有 $r$ 个房间住 $k+1$ 人，其余 $m-r$ 个房间住 $k$ 人，可安排总数为 $mk + r = n$，剩余 0。