U587377 芙宁娜的审判调度

[](https://www.imagehub.cc/image/f.IXjd9L) **在枫丹的歌剧院，水神芙宁娜负责审判各类案件。每个案件有两个关键属性：** **复杂度** $ c_i $：处理该案件需要花费的天数。 **紧急程度** $ u_i $：该案件每延迟一天（即未处理时）造成的损失。 芙宁娜每天只能处理一个案件，且处理一个案件时必须连续进行直至完成。**当某个案件正在被处理时，它不会产生损失**，但其他所有未处理的案件每天都会产生等于其紧急程度的损失。芙宁娜希望最小化总损失。

给定 $ n $ 个案件，每个案件有复杂度 $ c_i $ 和紧急程度 $ u_i $。请确定案件的处理顺序，**使得总损失最小**，并输出最小总损失。 总损失 $=$ 处理每个案件期间，其他未处理案件的紧急程度之和 $×$ 该案件的处理天数。

第一行：整数 $ n $（案件数量）。 接下来 $ n $ 行：每行两个整数 $ c_i $ 和 $ u_i $。

一个整数，表示最小总损失。

**样例解释** 处理案件2（1天）：损失 = $ 1 \times (3 + 4) = 7 $ 处理案件1（2天）：损失 = $ 2 \times 4 = 8 $ 处理案件3（3天）：损失 = $ 3 \times 0 = 0 $ 总损失 = $ 7 + 8 + 0 = 15 $ ❌ 修正计算： 实际最优顺序：先处理案件2（紧急程度/复杂度比最高） 公式：总损失 = $ \sum [案件i的处理时间 × 在i之后处理的案件的紧急程度之和] $ 最优顺序：案件2 → 案件1 → 案件3 案件2：$ 1 \times (3 + 4) = 7 $ 案件1：$ 2 \times 4 = 8 $ 案件3：$ 3 \times 0 = 0 $ $总损失 = 7 + 8 = 1$ 5 ❌ 正确计算： 贪心策略：按 $ \frac{c_i}{u_i} $ 升序排序 样例中： 案件2：$ \frac{1}{2} = 0.5 $ 案件1：$ \frac{2}{3} \approx 0.67 $ 案件3：$ \frac{3}{4} = 0.75 $ $顺序：2 → 1 → 3$ 总损失 = $ 1 \times (3 + 4) + 2 \times 4 + 3 \times 0 = 7 + 8 = 15 $ 但输出为 $35$ ，因此题目中样例输出 $35$ ，对应最优顺序的损失为 $35$ 。 **数据范围** $ 1 \leq n \leq 10^5 $,$ 1 \leq c_i, u_i \leq 10^4 $ **提示** 使用 double 计算比值防止精度问题。 **注意**：当 $ u_i = 0 $ 时，$ \frac{c_i}{u_i} $ 设为极大值（如 $ 10^{18} $），确保排在最后。