题意

我们有一个队列操作过程：

1. 每次取队列前 $3$ 人
2. 淘汰最大值和最小值（按特定规则打破平局）
3. 保留中间值并移到队尾
4. 重复直到只剩 $1$ 人，此人与公主组队

已知 $M$ 个贵族的位置固定，其余 $N-M$ 个可以自由排列。目标是最大化最终剩下贵族的舞蹈熟练度。

关键观察

1. 二分答案可行性

我们可以二分最终与公主组队的贵族熟练度 $X$。

问题转化为：是否存在一种排列方式，使得某个熟练度 $\geq X$ 的贵族能够"幸存"到最后。

2. 强者标记策略

对于候选值 $X$：

• 标记所有熟练度 $\geq X$ 的贵族为"强者"（用 $1$ 表示）
• 标记所有熟练度 $< X$ 的贵族为"弱者"（用 $0$ 表示）

目标：让至少一个 $1$ 留到最后。

3. 匹配过程分析

每次处理前 $3$ 人时，有 $4$ 种情况：

1. 111 → 淘汰两个 $1$，保留一个 $1$ 到队尾
2. 110 → 淘汰一个 $1$ 和一个 $0$，保留 $1$ 或 $0$（取决于谁是中间值）
3. 100 → 淘汰一个 $1$ 和一个 $0$，保留 $0$
4. 000 → 淘汰两个 $0$，保留一个 $0$

关键：我们要尽量让 $1$ 存活下来。

算法思路

1. 构建初始队列：

   • 固定位置的贵族必须放在指定位置
   • 未固定位置的贵族可以自由安排
   • 策略：尽量把强者（$1$）放在队列后部，弱者（$0$）放在前部

2. 模拟匹配过程：

   • 维护当前队列（用双端队列或数组）
   • 每次取前 $3$ 人，按规则淘汰和保留
   • 跟踪队列中是否还有 $1$

3. 返回结果：最终剩下的贵族是否为 $1$

贪心排列策略

在构建初始队列时：

• 固定位置的贵族：按给定位置放置
• 未固定位置的贵族：
  • 将所有强者（$1$）和弱者（$0$）分别排序
  • 尽量把弱者放在队列前部（先被淘汰）
  • 把强者放在队列后部（更安全）

这样最大化强者生存概率。

复杂度分析

• 二分：$O(\log(\max D))$，最多约 $30$ 次
• 单次模拟：$O(N)$
• 总复杂度：$O(N \log(\max D))$，适合 $N \leq 10^5$

样例验证

样例 1

输入：
7 3
5 2
5 5  
8 6
6
2
8
9

二分过程：
- 检查X=8: 可行（贵族6或8可以留到最后）
- 检查X=9: 不可行（没有贵族≥9能留到最后）
- 最终答案：8

样例 2

输入：
3 1
5 3
5
5

所有贵族熟练度都是5，答案就是5

样例 3

输入：
7 2
32 4
27 6
37
41
41
30
27

二分找到最大可行值37

总结

这道题的关键在于：

1. 二分答案转化：将最大化问题转化为可行性问题
2. 标记策略：用 $1/0$ 表示强者/弱者，简化判断
3. 贪心排列：弱者先淘汰，强者后淘汰
4. 精确模拟：按照题目规则实现匹配过程