tgoop.com/cpluspluc/1064
Create:
Last Update:
Last Update:
🎯 ▪ Задача: "Числа-близнецы с кастомным компаратором" (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, чтобы избежать сортировки массивов и упростить логику поиска ближайших чисел.
BY C++ Academy
Share with your friend now:
tgoop.com/cpluspluc/1064