gpt-3.5-turbo-0613· OpenAI WildChat-4.8M (AI2)
Даны два массива: a длиной n и b длиной m (1<=m<=n<=10^5). Скажите, можно ли удалить n −…
- User
Даны два массива: a длиной n и b длиной m (1<=m<=n<=10^5). Скажите, можно ли удалить n − m произвольных элементов из массива a так, чтобы после их удаления для каждого индекса i выполнялось условие bi<=ai. Формат входных данных Первая строка содержит два целых числа n и m — размеры массивов. Вторая строка содержит n целых чисел ai (1<=ai<=10^9). Третья строка содержит m целых чисел bi (1<=bi<=10^9). Формат выходных данных Выведите «yes», если можно удалить элементы описанным образом, иначе — «no». Реши задачу на с++
- Assistant
#include <iostream> #include <vector> #include <algorithm> int main() { int n, m; std::cin >> n >> m; std::vector<int> a(n); std::vector<int> b(m); for (int i = 0; i < n; i++) { std::cin >> a[i]; } for (int i = 0; i < m; i++) { std::cin >> b[i]; } std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end()); int aIndex = n - 1; int bIndex = m - 1; while (aIndex >= 0 && bIndex >= 0) { if (a[aIndex] >= b[bIndex]) { aIndex--; bIndex--; } else { aIndex--; } } if (bIndex < 0) { std::cout << "yes" << std::endl; } else { std::cout << "no" << std::endl; } return 0; }Алгоритм решения следующий:
- Считываем размеры массивов n и m.
- Считываем элементы массивов a и b.
- Сортируем оба массива по возрастанию.
- Инициализируем два индекса aIndex и bIndex, которые указывают на конец каждого массива.
- Запускаем цикл while, который будет сравнивать элементы массивов с конца.
- Если a[aIndex] >= b[bIndex], то увеличиваем aIndex и bIndex на один.
- Если a[aIndex] < b[bIndex], то увеличиваем только aIndex на один.
- Если bIndex < 0, то значит удаление элементов из массива a возможно, иначе удаление невозможно.
- Выводим результат "yes" или "no".