给出长度为n的正整数序列{an}和{bn}。对于每个ai（1≤i≤n），进行恰好一次以下操作：
将ai 变成满足|ai−x|≤k×bi 的任意整数x。
请你求出最小的非负整数k，使得存在至少一种方法使得操作后序列{an}所有数都相等。
问题 D: 有效算法
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 32
[提交][状态][讨论版][命题人:]
题目描述
输入描述
本题测试点包含多组数据
第一行包含一个正整数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
第一行包含一个正整数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。
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版