C++ Academy

🎯 ▪ Задача: "Числа-близнецы с кастомным компаратором" (C++ для продвинутых)

У вас есть массив N целых чисел. Нужно найти все пары чисел (A, B), таких что:

1. |A - B| минимально среди всех пар в массиве
2. A — четное, а B — нечетное
3. Если таких пар несколько, вернуть все, отсортированные по A, затем по B

▪ Ограничения:
- 1 <= N <= 10^5
- -10^9 <= A[i] <= 10^9

▪ Пример:

Вход:

arr = [4, 7, 9, 2, 8, 3]

Вывод:

(2,3)
(4,3)
(4,7)
(8,7)
(8,9)

✅ Минимальная разница = 1

🧠 Уловки задачи:

Наивное сравнение O(N²) слишком медленно

Нужно использовать сортировку + два указателя или бинарный поиск

✍️ Решение:

Идея решения — сначала разделить все числа на четные и нечетные, отсортировать их, а затем с помощью двух указателей найти пары с минимальной разницей. После этого собрать все такие пары и отсортировать результат по условию.

▪ Код:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
int N;
cin >> N;
vector<int> even, odd;

for (int i = 0; i < N; ++i) {
int x;
cin >> x;
if (x % 2 == 0) even.push_back(x);
else odd.push_back(x);
}

sort(even.begin(), even.end());
sort(odd.begin(), odd.end());

vector<pair<int, int>> result;
int min_diff = INT_MAX;

int i = 0, j = 0;
while (i < even.size() && j < odd.size()) {
int a = even[i];
int b = odd[j];
int diff = abs(a - b);

if (diff < min_diff) {
min_diff = diff;
result.clear();
result.emplace_back(a, b);
} else if (diff == min_diff) {
result.emplace_back(a, b);
}

if (a < b) i++;
else j++;
}

sort(result.begin(), result.end());

for (auto& p : result) {
cout << "(" << p.first << "," << p.second << ")\n";
}

return 0;
}```

▪ 🔍 Пошаговый разбор:

✅ Считываем входные данные

✅ Разделяем числа на четные и нечетные

✅ Сортируем оба массива

✅ Используем два указателя, чтобы найти минимальную разницу за O(N)

✅ Если нашли пару с меньшей разницей — сбрасываем результат и добавляем её

✅ Если нашли пару с такой же разницей — просто добавляем

✅ Финально сортируем все найденные пары по A, затем по B

✨ Почему задача хитрая: ✅ Нужно оптимальное решение вместо лобового перебора
✅ Включает тонкую работу с индексами
✅ Требует правильно обрабатывать несколько минимальных пар
✅ Объединяет знания сортировки, двух указателей и поиска пар

💪 Challenge для профи: 👉 Попробуйте реализовать эту задачу с помощью multiset + lower_bound / upper_bound, чтобы избежать сортировки массивов и упростить логику поиска ближайших чисел.

www.tgoop.com/cpluspluc/1064

3.6K viewsMay 6 at 11:03

🎯 ▪ Задача: "Числа-близнецы с кастомным компаратором" (C++ для продвинутых)

У вас есть массив N целых чисел. Нужно найти все пары чисел (A, B), таких что:

1. |A - B| минимально среди всех пар в массиве
2. A — четное, а B — нечетное
3. Если таких пар несколько, вернуть все, отсортированные по A, затем по B

▪ Ограничения:
- 1 <= N <= 10^5
- -10^9 <= A[i] <= 10^9

▪ Пример:

Вход:

arr = [4, 7, 9, 2, 8, 3]

(2,3)
(4,3)
(4,7)
(8,7)
(8,9)

BY C++ Academy