Infinite Knapsack

题目描述

有 $N$$$种物品，每种物品有无限多个拷贝。第 $i$ 种物品的重量为 $A_i$，体积为 $B_i$，价值为 $C_i$。 等级为 $X$ 的高桥可以携带总重量不超过 $X$ 且总体积不超过 $X$ 的物品。在此条件下，可以携带任意数量的同种物品，也可以省略某些种类的物品。 记 $f(X)$ 为等级 $X$ 的高桥能携带的物品的最大总价值。可以证明极限 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ 存在。求这个极限。

输入格式

输入由标准输入按以下格式提供： $N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$

输出格式

输出答案。当你的输出与裁判的答案的绝对或相对误差不超过 $10^{-6}$ 时，将被视为正确。

2
100000000 200000000 100000000
200000000 100000000 100000000

0.6666666666666667

1
500000000 300000000 123456789

0.2469135780000000

提示

$1\leq N\leq 2\times 10^5$ $10^8\leq A_i,B_i,C_i \leq 10^9$ 输入中的所有数值都是整数。当 $X=300000000$ 时，高桥可以携带总重量不超过 $300000000$ 且总体积不超过 $300000000$ 的物品。 例如，他可以携带一件第 $1$ 种物品和一件第 $2$ 种物品。则物品的总价值为 $100000000+100000000=200000000$。这是能达到的最大价值，所以 $\dfrac{f(300000000)}{300000000}=\dfrac{2}{3}$。 同样也可证明 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ 等于 $\dfrac{2}{3}$。因此，答案是 $0.6666666\ldots$。

标签: AtCoder|abc275G

来源

AtCoder|abc275G