题解 CF639E 【Bear and Paradox】

> [CF639E Bear and Paradox](https://codeforces.com/contest/639/problem/E) ## 题意 - 有 $n$ 个问题，第 $i$ 个问题的初始得分为 $p_i$，所花费的时间为 $t_i$。 - 设 $T = \sum_{i=1}^n t_i$，你可以按照某个顺序恰好花费 $T$ 时间完成所有问题。 - 若你在时刻 $x$ 完成了问题 $i$，你可以得到 $p_i \cdot (1 - \frac{cx}T)$ 的得分，其中 $c$ 是一个 $[0,1]$ 的实数。 - 对于每个 $c$，都存在至少一个可以使得分最大的最佳做题顺序。 - 对于一个做题顺序，若出现了两个问题 $i,j$ 满足 $p_i < p_j$ 但 $i$ 的得分严格大于 $j$ 的得分，则认为这种做题顺序存在悖论。 - 你需要求出最大的 $c$，使得这个 $c$ 对应的任意最佳做题顺序都不存在悖论。 - $n \le 1.5 \times 10^5$，$p_i,t_i \le 10^8$，答案精度误差 $\le 10^{-6}$。 ## 题解 最佳做题顺序一定是按照 $\frac{p_i}{t_i}$ 从大到小排序的，在所有 $\frac{p_i}{t_i}$ 都不相同的情况下，设排序后第 $i$ 个问题的得分为 $p_i - \frac{p_i\sum_{j=1}^{i}t_j}{T}c$，即有 $n$ 个关于 $c$ 的一次函数。 题目要求不存在悖论，等价于最大的 $c$ 满足这 $n$ 个一次函数在 $(0,c)$ 中不存在交点。 找到对于每个相同的 $p_i$ 最靠上和最靠下的一次函数，解出相邻两个 $p_i$ 对应的函数交点，取最小的横坐标即可。 当有 $\frac{p_i}{t_i}$ 相同的时候，会出现有多个最佳做题顺序，因此需要找到每道题对应的一次函数的斜率的最大和最小值。 时间复杂度 $\mathcal O(n \log n)$。 ## 代码 ```cpp const int N = 1.5e5 + 7; const ld eps = 1e-10L; int n; ll T, s; struct P { int p, t; ld x, l, r; inline bool operator < (const P &o) const { return x > o.x; } } p[N]; int main() { rd(n); for (int i = 1; i <= n; i++) rd(p[i].p); for (int i = 1; i <= n; i++) rd(p[i].t), p[i].x = 1.0L * p[i].p / p[i].t, T += p[i].t; sort(p + 1, p + n + 1); for (int i = 1, j = 0; i <= n; i = j + 1) { while (j + 1 <= n && abs(p[i].x - p[j+1].x) < eps) ++j; for (int k = i; k <= j; k++) p[k].l = 1.0L * p[k].p * (s + p[k].t) / T; for (int k = i; k <= j; k++) s += p[k].t; for (int k = i; k <= j; k++) p[k].r = 1.0L * p[k].p * s / T; } sort(p + 1, p + n + 1, [&](P x, P y) { return x.p < y.p; }); ld ans = 1; for (int i = 1; i < n; i++) if (p[i].p < p[i+1].p) { ld l = 1e8L, r = 0.0L; int j = i; while (j && p[j].p == p[i].p) l = min(l, p[j--].l); j = i + 1; while (j <= n && p[j].p == p[i+1].p) r = max(r, p[j++].r); if (l + eps < r) ans = min(ans, (p[i].p - p[i+1].p) / (l - r)); } printf("%.10Lf\n", ans); return 0; } ```