CF639E Bear and Paradox

Limak 是一只大北极熊。他为一次算法比赛准备了 $n$ 道题目。第 $i$ 道题的初始分数为 $p_{i}$。测试者还说，第 $i$ 道题需要 $t_{i}$ 分钟来解决。题目的难度不一定和编号有关，可能更难的题目初始得分更少，但现在更改初始得分已经来不及了——Limak 已经公布了每道题目的初始分数。不过，他仍可以调整失分的速度，即本题中的 $c$。 设 $T$ 为解全部题目需要的总时间（即 $T = t_1 + t_2 + \cdots + t_n$）。比赛时长正好为 $T$ 分钟，也就是说刚好可以完成所有题目。 每道题目的得分会线性递减。当在第 $x$ 分钟完成第 $i$ 道题时，可以获得恰好 $p_{i}\cdot (1 - c\cdot \frac{x}{T})$ 分。如果分数为负，可以视为 $0$。 假设 $c$ 已确定。在比赛中，参赛者可以选择任意顺序解决题目。共有 $n!$ 种不同做题顺序，每一种都会带来一定的总分（可以不是整数）。我们定义某个顺序为最优顺序，如果该顺序获得的总分最大，也就是，采用该顺序的总得分大于等于其它所有顺序的得分。显然至少存在一种最优顺序，也可能有多种。 Limak 假设每个参赛者在一开始都能准确估算出 $t_{i}$ 并选择某种最优解题顺序。他还假设测试者对每道题目所需时间的预测全部准确。 对于任意满足 $p_i < p_j$ 的两道题 $i$ 和 $j$，如果某个参赛者在题目 $i$ 上拿到的分比在 $j$ 上得分严格高，那么 Limak 会感到不高兴——他称之为“悖论”。 很容易证明，当 $c=0$ 时不会有这样的悖论。但当 $c$ 增大时，情况可能变坏。求最大的实数 $c$，使得无论如何选择最优解题顺序，都不会出现悖论（即不会存在在任意一种最优顺序下出现“悖论”的 $c$）？ 可以证明，这个最大值一定存在。

第一行包含一个整数 $n$（$2\leq n\leq 150000$），表示题目数量。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1\leq p_i \leq 10^8$），表示每道题的初始分数。 第三行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$（$1\leq t_i \leq 10^8$），其中 $t_i$ 表示第 $i$ 道题需要的时间。

输出一个实数，表示最大的 $c$ 值（即最大无悖论的 $c$，具体见题面）。只需输出一行。你的答案将被认为是正确的，当且仅当其相对误差或绝对误差不超过 $10^{-6}$。 即，假如你的答案为 $a$，标准答案为 $b$，则当 $|a-b| / \max\{1, |b|\} \le 10^{-6}$ 时认为正确。

在第一个样例中，共有 $3$ 道题目，分别为 $(4,1)$（初始分数为 $4$，耗时 $1$ 分钟）、$(3,1)$ 和 $(10,8)$。总时间为 $T=1+1+8=10$。 验证当 $c=0.7$ 时会有悖论。按照 $1,2,3$ 的顺序解题，可以取得最高总分： 1. 在第 $1$ 分钟完成第 $1$ 题：得分为 $4 \times (1 - 0.7 \times 1 / 10) = 3.72$ 2. 在第 $2$ 分钟完成第 $2$ 题：得分为 $3 \times (1 - 0.7 \times 2 / 10) = 2.58$ 3. 在第 $10$ 分钟完成第 $3$ 题：得分为 $10 \times (1 - 0.7 \times 10 / 10) = 3$ 这个顺序总分为 $3.72 + 2.58 + 3 = 9.3$，并且这是唯一的最优顺序（你可以尝试其它 $5$ 种顺序，总分都更低）。注意看 $1$ 和 $3$，有 $4 < 10$ 但 $3.72 > 3$，出现了悖论。实际上，对于 $c=0.625$ 没有悖论，但 $c$ 大于这个值时都会出现悖论。 第二个样例中，所有 $24$ 种顺序都是最优顺序。 第三个样例中，即使 $c=1$ 也不会出现悖论。 由 ChatGPT 5 翻译