CF639E Bear and Paradox 题解

CF639E Bear and Paradox

题意

• 有 $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)$。

代码

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;
}