问题分析

我们有 $2N$ 个人（M 和 F）要在 $N$ 分钟内通过两个窗口（男装、女装）完成发放。关键规则是：

• F 优先去女装窗口，女装满才去男装窗口
• M 优先去男装窗口，男装满且女装空时让位给后面的 F

Dark 值定义为：原序列中在某人后面，新序列中在他前面的人数。

我们需要找到一种重排方案，使得最大 Dark 值最小。

关键观察

1. 时间约束分析

• 每分钟最多处理 2 人（两个窗口各 1 人）
• $N$ 分钟最多处理 $2N$ 人 → 必须每分钟都处理满 2 人
• 如果无法满足这个条件，输出 -1

2. F 的数量限制

设总 F 数量为 $F_{\text{total}}$，总 M 数量为 $M_{\text{total}}$，有：

必要条件：$F_{\text{total}} \leq N$

• 因为女装窗口每分钟只能处理 1 个 F
• 如果 $F_{\text{total}} > N$，不可能在 $N$ 分钟内完成

3. Dark 值的意义

对于位置 $i$ 的人：

• 原序列中在他后面的人：$2N - i - 1$ 个
• 新序列中在他前面的人：$j$ 个（新位置）
• Dark 值 = 原后面且新前面的人数

最大 Dark 值最小化 → 尽量减少"跳跃"很大的人

二分答案框架

我们二分答案 $K$：判断是否存在重排方案使得最大 Dark 值 $\leq K$。

可行性检查

对于给定的 $K$，我们模拟发放过程，同时检查 Dark 值约束。

设原序列为 $S$，新序列为 $T$。

Dark 值约束：对于新序列中第 $i$ 个人（从 0 开始），他在原序列中的位置为 $p_i$，那么：

• 原序列中在他后面的人：所有位置 $> p_i$ 的人
• 新序列中在他前面的人：位置 $< i$ 的人
• Dark 值 = 满足 $j > p_i$ 且在新序列中位置 $< i$ 的人数

这个约束很难直接处理，我们转化为：

等价条件：对于原序列中的每个人，在新序列中最多有 $K$ 个原本在他后面的人跑到他前面。

贪心调度算法

我们维护两个队列：

• free_F：可以自由安排位置的 F（Dark 值约束允许）
• free_M：可以自由安排位置的 M

同时维护原序列的指针，按原顺序考虑每个人。

算法步骤：

1. 初始化：free_F = [], free_M = [], ptr = 0（原序列指针）

2. 对于每个时间步 $t = 0$ 到 $N-1$：

   • 尝试安排 2 个人到两个窗口
   • 优先安排 F 到女装窗口：
     • 如果 free_F 非空，取一个 F
     • 否则如果原序列 ptr 位置是 F 且 Dark 值约束允许，取这个 F
   • 安排 M 到男装窗口（或 F 如果女装满）：
     • 类似逻辑，但要检查 Dark 值约束
   • 更新 ptr 和队列

3. Dark 值约束检查：

   • 当从原序列中取一个位置 $p$ 的人放到新位置 $i$ 时
   • 检查：原序列中在 $p$ 前面的人中，有多少已经放到新序列中 $i$ 后面
   • 如果这个数 $> K$，则违反约束