Problem Statement
给出长度为n的正整数序列{an}和{bn}。对于每个ai（1≤i≤n），进行恰好一次以下操作： • 将ai 变成满足|ai−x|≤k×bi 的任意整数x。 请你求出最小的非负整数k，使得存在至少一种方法使得操作后序列{an}所有数都相等
本.题 .测 .试 .点 .包 .含 .多 .组 .数 .据。 第一行包含一个正整数T（1≤T ≤1.5×10^5），表示数据组数。 对于每组数据： 第一行包含一个正整数n（2≤n≤3×10^5）。 第二行包含n个正整数a1,a2,…,an（1≤ai ≤109）。 第三行包含n个正整数b1,b2,…,bn（1≤bi ≤10^9）。 保证单个测试点中所有数据的∑n≤3× 105。
Output
对于每组数据： 输出一行一个整数，表示答案。
Solving
考虑二分答案，观察到对于每一个 a[i] 其可转换为元素大小的范围为[a[i]-k*b[i],a[i]+k*b[i]]
所以只需判断二分得到的K的条件下每一个a[i]是否至少有一个重合覆盖点即可，即比较所有边界的最大左边界是否小于等于最小右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
int n;
bool check(int x,vector<int>& a,vector<int>& b)
{
int minright = LLONG_MAX;
int maxleft = LLONG_MIN;
for(int i=1;i<=n;i++)
{
maxleft = max(maxleft,a[i]-x*b[i]);
minright = min(minright,a[i]+x*b[i]);
}
return maxleft <= minright;//返回是否满足条件 找到满足条件的第一个K
}
void solve()
{
cin >> n;
vector<int> a(n+1);
vector<int> b(n+1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i];
int l = 0,r = 1e9,mid;
while(l+1<r)
{
mid = l + r >> 1;
if(check(mid,a,b)) r = mid;
else l = mid;
}
if(!check(l,a,b)) l = r;
cout << l << endl;
}
|