Responsive image

问题 D: 有效算法

问题 D: 有效算法

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 32
[提交][状态][讨论版][命题人:]

题目描述

给出长度为n的正整数序列{an}和{bn}。对于每个ai（1≤i≤n），进行恰好一次以下操作：
将ai 变成满足|ai−x|≤k×bi 的任意整数x。 
请你求出最小的非负整数k，使得存在至少一种方法使得操作后序列{an}所有数都相等。

输入描述

本题测试点包含多组数据
第一行包含一个正整数T（1≤T ≤1.5×1e5），表示数据组数
对于每组数据： 第一行包含一个正整数n（2≤n≤3×1e5) 
第二行包含n个正整数a1,a2,...,an（1≤ai ≤1e9)
第三行包含n个正整数b1,b2,...,bn（1≤bi ≤1e9)
保证单个测试点中所有数据的∑n≤3× 1e5

输出描述

对于每组数据： 
输出一行一个整数，表示答案。

样例输入

2
4
8 3 3 5
1 2 3 2
5
4 3 4 5 6
3 1 3 1 1

样例输出

2
2

提示

对于样例一，可以令ai 全变为6。

对于样例二，可以令ai 全变为5。

[提交][状态]
ACM算法攻关部