当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6637:Speed Dog

题目描述
Sunset and Elephant formed a programming contest team named ``Speed Dog''. There are $n$ problems in the online judge, labeled by $1,2,\dots,n$.

For the $i$-th problem, Sunset needs to code $a_i$ bytes while Elephant needs to code $b_i$ bytes. But they can work on problems together. Specifically, for the $i$-th problem, they can choose a real number $x_i(0\leq x_i\leq 1)$, split this problem into two parts $A$ and $B$, then assign Sunset to code part $A$ and assign Elephant to code part $B$. As a result, Sunset will code $a_i\times x_i$ bytes, and Elephant will code $b_i\times(1-x_i)$ bytes.

Now they want to solve all the problems whose labels are not larger than $k$. Assume Sunset codes $X$ bytes in total and Elephant codes $Y$ bytes in total. It is too tired for a coder to code too much code. Please help them find an assignment that $\max(X,Y)$ is minimized.
输入解释
The first line of the input contains an integer $T(1\leq T\leq 10000)$, denoting the number of test cases.

In each test case, there is one integer $n(1\leq n\leq 250000)$ in the first line, denoting the number of problems.

For the next $n$ lines, each line contains two integers $a_i,b_i(1\leq a_i,b_i\leq 1000)$, denoting each problem.

It is guaranteed that $\sum n\leq 10^6$.
输出解释
For each test case, print $n$ lines in format $\texttt{u/v}$, where the $i$-th line denotes the minimum value of $\max(X,Y)$ when $k=i$. Note that you should guarantee that $\gcd(u,v)=1$.
输入样例
1
3
1 3
3 1
2 2
输出样例
3/4
1/1
2/1
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6637

最后修改于 2020-10-25T23:33:03+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/4000MS(Java/Others) 524288/524288K(Java/Others)