题目解析：新生儿看护调度问题

问题理解

这是一个关于多人协作照顾新生儿的时间调度问题。我们需要在保证任何时刻都至少有一人看护婴儿的前提下，让每个人都能睡同样长的时间T，并最大化T的值。

关键约束条件：

• 有n个人，时间区间[0,L)被分成L个单位时间片
• 每个人在每个时间片可能是忙碌(X)或空闲(.)
• 每个人只能睡一次连续的时间T
• 在任何时刻x∈[0,L)，至少有一个空闲且没有睡觉的人在看护
• 目标是找到最大的T，以最简分数形式输出

算法思路

1. 初步检查

首先检查是否存在某个时间片所有人都忙碌，如果是则直接输出-1，因为该时刻无法保证有人看护。

2. 分数枚举与二分查找

由于T必须是有理数，我们预先生成所有可能的不可约分数(分子分母互质)，并按值排序。然后使用二分查找在这些分数中寻找最大的可行T。

3. 可行性检查

对于每个候选分数T=X/Y，使用深度优先搜索(DFS)尝试安排每个人的睡眠时间：

预处理数组：

• c[j]：时间片j上空闲的人数
• f[i][j]：从时间片j开始，满足条件(空闲人数≤i)的连续时间片长度
• d[i][j]：第i个人从时间片j开始的连续空闲时间片数
• g[i][j]：第i个人从时间片j开始，第一个满足睡眠要求的位置

DFS过程：

• 使用位掩码跟踪已安排睡眠的人
• 对于每个未安排的人，计算其最早可开始睡眠的时间
• 采用贪心策略，优先选择最早可开始睡眠的人
• 记录最佳和次佳选择，提高搜索效率

4. 时间处理技巧

由于睡眠时间可能落在时间片内部，代码中将时间乘以分母Y，用整数运算避免浮点数精度问题。

复杂度分析

• 预处理：O(n×L)，可接受
• 分数生成：O(m×n)，其中m=L
• 二分查找：O(log(m×n))
• DFS验证：最坏O(2^n)，但由于n≤18且使用剪枝，实际可接受

关键洞察

1. 问题转化：将连续时间调度问题转化为离散时间片上的覆盖问题
2. 分数处理：通过预生成互质分数避免浮点数精度问题
3. 状态压缩：利用n较小的特点，使用位掩码高效表示状态
4. 贪心剪枝：在DFS中优先选择最早可开始睡眠的人，有效减少搜索空间

样例验证

样例1：

输入：

3 6
..X.XX
.X..X.
X..X..

输出：4/3

验证：存在安排方案使每个人睡4/3单位时间，且任何时刻都有人看护。

样例2：

输入：

3 2
..
XX
..

输出：0/1

验证：第二个人始终忙碌，其他人不能睡觉。

样例3：

输入：

1 3
.X.

输出：-1

验证：在时刻x≈1.57，没有人能照顾婴儿。

总结

该问题通过结合二分查找、状态压缩DFS和贪心策略，高效地解决了在复杂约束下的公平调度问题。算法充分利用了问题规模的特点(n小L大)，通过巧妙的预处理和状态表示，在可接受的时间内找到了最优解。