Проблема: Пара целых чисел (x,y) является идеальной, если выполняются оба следующих условия:
- мин(|х-у|,|х+у|)‹=мин(|х|,|у|)
- max(|x-y|,|x+y|)›=max(|x|,|y|)
Для заданного массива длины n найдите количество идеальных пар (arr[i], arr[j]), где 0‹=i‹j‹n
Здесь min(a,b) — минимальное значение a и b, max(a,b) — максимальное значение a и b, а |x| является абсолютным значением x.
Пример:
обр = [-9,6, -2,1] -> ответ = 2
обр = [2,5, -3] - > ответ = 2
Как решить это с временной сложностью меньше, чем O (n²)?
void callPerfectPairs(vector<int> v, int n) {
//|y| <= 2 * |x| where x < y
sort(v.begin(), v.end());
//binary search for satisfying above condition
//or two pointer approach
int i, j;
int res = 0;
//condition valid x < y
i = j = 0;
while (i < n && j < n) {
if (i == j) j++;
else if (i < j && 2*i<j) i++;
else if (i < j && 2*i >= j) {
res+=(j-i);
j++;
}
}
cout <<res <<endl;
}
int main() {
int n;
cin>>n;
vector<int> v;
for (int i = 0; i < n; i++) {
int j;
cin>>j;
v.push_back(j);
}
callPerfectPairs(v, n);
}
/**
min(|x-y|,|x+y|)<=min(|x|,|y|)
max(|x-y|,|x+y|)>=max(|x|,|y|)
0<=i<j<n for (arr[i], arr[j])
The condition is matters only when we talk about indexes in the result
min(|x-y|, |x+y|) > 0 (Always) ... |x-y| > 0 and |x+y| > 0 ...
min
x < 0, y > 0 ... |x+y| ... ||x|-|y||
x > 0, y < 0 ... |x+y| ... ||x|-|y||
x > 0, y > 0 ... |x-y| ... ||x|-|y||
x < 0, y < 0 ... |x-y| ... ||x|-|y||
--- ||x|-|y||
max(|x-y|, |x+y|) > 0 (Always) ... ||x|+|y|| > |x| || |y| (always)
min(|x-y|, |x+y|) = ||x|-|y|| < min(|x|, |y|)
||x|-|y|| <= |y| when x > y as always min considered
or |y| - |x| <= |x|
|y|-|x| <= |x|
|y| <= 2 * |x| when y > x
-9 6 -2 1
1,2 1,6 1,9 2,6 2,9 6,9 - check possible
1,2 1,3
1,6 5,7
1 2 6 9 10 12 14
2 4 12 18
logic 12 >= 9 --- 6,9 valid pair j,i --- j-i
logic 2 >= 2 --- 1,2 valid pair j,i --- j-i
Final
1. sort and positive
|y| < 2|x| where |x|>|y|
window logic
i = j then j++ as i != j
i < j if 2 * i < j < j+1 < j+2
if 2 * i >= j then res += j-i and j++;
*/
