1115: 蒜头君的银行业务
Description
在银行柜台前，有 n 个顾客排队办理业务。 队伍中从前往后，第 i 位顾客办理业务需要ti 分钟时间。 一位顾客的等待时间定义为：队伍中在他之前的所有顾客和他自己的办理业务时间的总和。第 i 位顾客有一个最长等待时间 di，如果超过了时间 di，业务还没有办理完成，那么这位顾客就会觉得不满意。 具体来说，假设第 i 位顾客的等待时间为 fi，若 fi > di， 则这位顾客的不满意度为 fi-di，否则不满意度为 0。
蒜头君作为银行里的职员，需要安排这 n 位顾客的初始排队顺序，使得不满意度最大的那位顾客不满意度最小
Input
输入的第 1 行包含一个正整数 n，表示顾客的数量。
输入的第 2 行包含 n 个正整数，第 i 个数表示 ti， 单位为分钟。
输入的第 3 行包含 n 个正整数，第 i 个数表示 di， 单位为分钟。
Output
输出包含 1 个整数，表示最大不满意度的最小值。
Sample Input Copy
3
5 8 10
11 15 13Sample Output Copy
8HINT
输入输出样例说明
|
排队顺序 |
1 |
3 |
2 |
|
业务办理时间 |
5 |
10 |
8 |
|
等待时间 |
5 |
15 |
23 |
|
最长等待时间 |
11 |
13 |
15 |
|
不满意度 |
0 |
2 |
8 |
最大不满意度为 8。 这是最大不满意度能达到的最小值。
数据规模
对于 50%的数据， n≤10
对于 70%的数据， n≤1,000
对于 100%的数据， n≤100,000， 1≤ti≤104， 0≤di≤109