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

建议使用的浏览器:

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

6773:King of Hot Pot

题目描述
Little Q is enjoying hot pot together with Tangjz. There are $n$ dishes of meat in the boiling water, labeled by $1,2,\dots,n$. The $i$-th dish of meat will be OK to eat at time $a_i$, and it will take Little Q $b_i$ units of time to swallow it. It is impossible for Little Q to swallow more than one dish of meat at the same moment. Note that for the $i$-th dish of meat, Little Q can choose to ignore it for a while and swallow it later.

Little Q is called "King of Hot Pot", and he wants to show off before Tangjz by swallowing $k$ dishes of meat as soon as possible. Please write a program to help Little Q find $k$ dishes of meat and the order to swallow them such that the time he spends on reaching the target is minimized for every possible value of $k$ ($1\leq k\leq n$). Note that the time for waiting is also included in the answer.
输入解释
The first line of the input contains a single integer $T$ ($1 \leq T \leq 10\,000$), the number of test cases.

For each case, the first line of the input contains an integer $n$ ($1 \leq n \leq 300\,000$), denoting the number of dishes of meat.

Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($1\leq a_i,b_i\leq
10^9$), denoting each dish of meat.

It is guaranteed that the sum of all $n$ is at most $1\,000\,000$.
输出解释
For each test case, output a single line containing $n$ integers, the $k$-th ($1\leq k\leq n$) of which denoting the minimum possible units of time needed for Little Q to swallow $k$ dishes of meat.
输入样例
1
5
1 2
4 6
3 5
4 2
3 2
输出样例
3 5 7 12 18
来自杭电HDUOJ的附加信息
Recommend liuyiding

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

源链接: HDU-6773

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

共提交 0

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