考点：二分

数据规模 n ≤ 50000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 50000
• 元素值域：a_i ≤ 1e3（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）
• 题目显式声明：复杂度要求 O(nlogn)、O(n)

解题思路

推荐方向：二分

本题切入点

分数先排序，分数线越低晋级越多、淘汰越少，具备单调性；枚举/二分分数线并检查两侧人数是否都落在 [x,y]。

把「求最优值」转化为「判定某值是否可行」，用单调性二分逼近答案。

思路框架（二分 通法 · 非本题专属）

1. 确认单调性：答案越大/越小，条件越容易（或越难）满足。
2. 写出 check(x)：判断值为 x 时是否可行。
3. 在答案区间 [lo, hi] 上二分，每次取 mid 调 check，收缩区间。
4. 边界收敛到唯一答案，注意取整方向（求最小可行值用上取整）。

实现要点：模板：while (lo < hi) { mid = (lo+hi)/2; if (check(mid)) hi = mid; else lo = mid+1; } 求最小可行值。

复杂度：时间 O(check 的代价 × log(答案范围)) ｜ 空间 O(1)

该范式的通法易错点

• check 函数不满足单调性却硬套二分（会得到错误答案）。
• 二分边界或取整方向写错，陷入死循环或漏掉边界答案。

对照本题

• 数据规模 n ≤ 50000，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

• 输入：6 2 3 / 1 2 3 4 5 6
• 输出：3