You are given array A with N number A= [a0, a1 .. aN-1] and array B with M numbers, B= [b0, b1 ... bM-1]. (1≤ N, M≤ 10 ^5,1 ≤ ais ≤ 10⁸, 1≤ bj ≤ 10⁸) SA and SB represent the respective scores of A and B, and each score is defined as the total score of the elements in each array. When calculating SA and SB this way, calculate D which makes the biggest difference between the two. (Caution: It is Not the absolute value) If there is more than one D that maximizes the difference between SA and SB, Calculate the smallest one.
Constraints
1 ≤ N, M ≤ 10⁵1 ≤ a_i ≤ 10⁸1 ≤ b_j ≤ 10⁸
Example 1
Input:
A = [6, 10, 9, 7, 8]
B = [4, 1, 5, 3, 2]Output:
5Explanation: When D is 5, the score of A and B are 10 and 5, respectively. Then, the value of SA-SB is 5 which is also maximum.
Example 2
Input:
A = [3, 2, 1]
B = [5, 6]Output:
0Explanation: When D is 0, the scores of A and B are 6 and 4 respectively. Then, the value of SA-SB is 2 which is also maximum.
Example 3
Input:
A = [10, 6, 3]
B = [3, 3, 10, 3, 2, 11]Output:
3Explanation: When D is 3, the scores of A and B are 5 and 8 respectively. Then, the value of SA-SB is -3 which is also maximum. Although the maximum value of SA-SB is -3 when D is 11 or 12 as the score of A and B are 3 and 6, respectively, the answer is 3 because 3 is smaller than 11.
Example 4
Input:
A = [1, 2]
B = [5, 6, 7, 8]Output:
8Explanation: When D is 8, the scores of A and B are 2 and 4 respectively. Then, the value of SA-SB is -2 which is also maximum. Remember that the difference between SA and SB is not an absolute value.
解法
枚举所有可能的 D(即 A∪B 中出现的值，以及"小于全部 A、B 元素的值"如 0 / min-1)。对每个候选 D，SA = sum A 中 ≥ D 的元素，SB 同理。把 A、B 各自排序后用前缀和，二分定位即可 O((N+M) log(N+M))。题目要求"最大化 SA - SB"，平局取最小 D。
from typing import List
from bisect import bisect_left
def findHiddenBenchmark(A: List[int], B: List[int]) -> int:
A_sorted = sorted(A)
B_sorted = sorted(B)
pa = [0] * (len(A) + 1)
pb = [0] * (len(B) + 1)
for i, v in enumerate(A_sorted): pa[i + 1] = pa[i] + v
for i, v in enumerate(B_sorted): pb[i + 1] = pb[i] + v
def score(arr, prefix, D):
i = bisect_left(arr, D)
return prefix[-1] - prefix[i]
candidates = sorted(set(A) | set(B) | {0, min(min(A), min(B))})
best_diff = -float('inf')
best_D = 0
for D in candidates:
diff = score(A_sorted, pa, D) - score(B_sorted, pb, D)
if diff > best_diff or (diff == best_diff and D < best_D):
best_diff = diff
best_D = D
return best_Dclass Solution {
int findHiddenBenchmark(int[] A, int[] B) {
int[] As = A.clone(), Bs = B.clone();
Arrays.sort(As); Arrays.sort(Bs);
long[] pa = new long[As.length + 1], pb = new long[Bs.length + 1];
for (int i = 0; i < As.length; i++) pa[i + 1] = pa[i] + As[i];
for (int i = 0; i < Bs.length; i++) pb[i + 1] = pb[i] + Bs[i];
TreeSet<Integer> set = new TreeSet<>();
for (int x : A) set.add(x);
for (int x : B) set.add(x);
set.add(0);
long bestDiff = Long.MIN_VALUE;
int bestD = 0;
for (int D : set) {
int ia = lowerBound(As, D), ib = lowerBound(Bs, D);
long sa = pa[As.length] - pa[ia];
long sb = pb[Bs.length] - pb[ib];
long diff = sa - sb;
if (diff > bestDiff || (diff == bestDiff && D < bestD)) {
bestDiff = diff;
bestD = D;
}
}
return bestD;
}
private int lowerBound(int[] a, int v) {
int lo = 0, hi = a.length;
while (lo < hi) {
int m = (lo + hi) >>> 1;
if (a[m] < v) lo = m + 1; else hi = m;
}
return lo;
}
}class Solution {
public:
int findHiddenBenchmark(vector<int>& A, vector<int>& B) {
vector<int> As = A, Bs = B;
sort(As.begin(), As.end()); sort(Bs.begin(), Bs.end());
vector<long long> pa(As.size() + 1), pb(Bs.size() + 1);
for (int i = 0; i < (int)As.size(); i++) pa[i + 1] = pa[i] + As[i];
for (int i = 0; i < (int)Bs.size(); i++) pb[i + 1] = pb[i] + Bs[i];
set<int> cands(A.begin(), A.end());
cands.insert(B.begin(), B.end());
cands.insert(0);
long long bestDiff = LLONG_MIN;
int bestD = 0;
for (int D : cands) {
int ia = lower_bound(As.begin(), As.end(), D) - As.begin();
int ib = lower_bound(Bs.begin(), Bs.end(), D) - Bs.begin();
long long sa = pa.back() - pa[ia], sb = pb.back() - pb[ib];
long long diff = sa - sb;
if (diff > bestDiff || (diff == bestDiff && D < bestD)) { bestDiff = diff; bestD = D; }
}
return bestD;
}
};Suppose there is a grid consisting of an infinite number of cells and you are standing on cell (0,0). Let your move strength be K which is initially set to 1. In one move you can perform the following operations: Move horizontally i.e. (x+k,y) from (x,y) Move vertically i.e. (x,y+k) from (x,y) Increase the value of K by 1 Find and print the minimum number of moves to reach the destination cell represented by (a,b). Input Each test contains multiple test cases. The first line contains the number of test cases t(1≤t≤10³). Description of the test cases follows. The first line and only line of each test case contain two-spaced integers a and b (1≤a,b≤10⁹). Output Print the minimum moves for each test case in separate lines.
Constraints
1 ≤ t ≤ 10³1 ≤ a, b ≤ 10⁹
Example 1
Input:
a = 1
b = 6Output:
5Explanation: For the first test case, First move to (1,0), then increase the value of K to 2, and then move three times to reach (1,6). Hence, it takes a total of 5.
Example 2
Input:
a = 1
b = 1Output:
2Explanation: :)
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理