7440: Hunting Monsters
内存限制：128 MB
时间限制：3 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
A group of N monsters has invaded into the town. You, as a guardian of the town, should protect the town from the attack of those monsters. As you are a smart warrior, you are going to eliminate K of them so that all the remaining monsters are scared and let them quit the town themselves.
In order to defeat a monster, you should consume A unit of energy while you restore B unit of energy after defeating it. If your energy before attack is less than A, you will be exterminated and the town will be ruined. These values A and B depends on the monster, so they may be distinct for different monsters. You may arbitrarily choose monsters to be killed. Note that you can defeat monsters in any order. You want to know the minimum amount of initial energy needed to kill at least K monsters. You are required to calculate the answer for all K=1⋯N.
In order to defeat a monster, you should consume A unit of energy while you restore B unit of energy after defeating it. If your energy before attack is less than A, you will be exterminated and the town will be ruined. These values A and B depends on the monster, so they may be distinct for different monsters. You may arbitrarily choose monsters to be killed. Note that you can defeat monsters in any order. You want to know the minimum amount of initial energy needed to kill at least K monsters. You are required to calculate the answer for all K=1⋯N.
输入格式
The first line of the input contains a single integer T (1≤T≤600), denoting the number of test cases. Each test case consists of 3 lines.
The first line of each test case contains a single integer N (1≤N≤3⋅105), the number of monsters. The next line contains N integers Ai (1≤Ai≤109), the amount of energy needed to defeat the ith monster. The third line contains N integers Bi (1≤Bi≤109), the amount of energy you will gain after killing the ith monster. It is guaranteed that the sum of N over all test cases does not exceed 2 500 000.
The first line of each test case contains a single integer N (1≤N≤3⋅105), the number of monsters. The next line contains N integers Ai (1≤Ai≤109), the amount of energy needed to defeat the ith monster. The third line contains N integers Bi (1≤Bi≤109), the amount of energy you will gain after killing the ith monster. It is guaranteed that the sum of N over all test cases does not exceed 2 500 000.
输出格式
Let ansK be the least initial energy needed to defeat K monsters.
You should calculate all ansK for K=1⋯N. In order to avoid huge output, you are only required to get the following.
For each test case, print a single integer E in a single line.
You should calculate all ansK for K=1⋯N. In order to avoid huge output, you are only required to get the following.
For each test case, print a single integer E in a single line.
输入样例 复制
2
3
2 3 1
1 5 4
4
1 2 3 4
1 1 2 3输出样例 复制
6
30数据范围与提示
Hint
For the first test case, ans[1,2,3]={1,1,1}.
For the second test case, ans[1,2,3,4]={1,2,3,4}.
For example, if you have 4 units of initial energy, you can kill the 4th, 3rd, 2nd and then 1st monster in order.
First you kill 4th monster, your energy will be 4-4+3=3.
Next, you attack 3rd monster, your energy will be 3-3+2=2.
After killing them, you kill 2nd one, then energy will become 2-2+1=1.
Finally, you can kill 1st one since your energy is not less than A_1.