Skip to content
The Chat Archive
gpt-3.5-turbo-0613· OpenAI WildChat-4.8M (AI2)

Даны два массива: a длиной n и b длиной m (1<=m<=n<=10^5). Скажите, можно ли удалить n −…

  1. 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». Реши задачу на с++

  2. 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;
    }
    

    Алгоритм решения следующий:

    1. Считываем размеры массивов n и m.
    2. Считываем элементы массивов a и b.
    3. Сортируем оба массива по возрастанию.
    4. Инициализируем два индекса aIndex и bIndex, которые указывают на конец каждого массива.
    5. Запускаем цикл while, который будет сравнивать элементы массивов с конца.
    6. Если a[aIndex] >= b[bIndex], то увеличиваем aIndex и bIndex на один.
    7. Если a[aIndex] < b[bIndex], то увеличиваем только aIndex на один.
    8. Если bIndex < 0, то значит удаление элементов из массива a возможно, иначе удаление невозможно.
    9. Выводим результат "yes" или "no".