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: :)
解法
设最终 K，需 K(K+1)/2 ≥ a+b(因为最优时把强度 1..K 拆给两个轴)。每次移动用一次强度后必须升级或继续；最简形式：升级 K-1 次 + 移动 K 次 = 2K-1 次。所以答案 = 2K-1，其中 K 是最小满足 K(K+1)/2 ≥ a+b 的正整数(可用二分或求根公式)。
def reachThePoint(a: int, b: int) -> int:
target = a + b
lo, hi = 1, 200000
while lo < hi:
m = (lo + hi) // 2
if m * (m + 1) // 2 >= target:
hi = m
else:
lo = m + 1
return 2 * lo - 1class Solution {
int reachThePoint(int a, int b) {
long target = (long) a + b;
long lo = 1, hi = 200000;
while (lo < hi) {
long m = (lo + hi) >>> 1;
if (m * (m + 1) / 2 >= target) hi = m;
else lo = m + 1;
}
return (int) (2 * lo - 1);
}
}class Solution {
public:
int reachThePoint(int a, int b) {
long long target = (long long) a + b;
long long lo = 1, hi = 200000;
while (lo < hi) {
long long m = (lo + hi) / 2;
if (m * (m + 1) / 2 >= target) hi = m;
else lo = m + 1;
}
return (int) (2 * lo - 1);
}
};