1. solvetop.com
  2. Информатика
  3. Используя C++, у вас есть...

Используя C++, у вас есть два списка чисел. Числа в первом списке упорядочены по неубыванию. Для каждого числа

  • 61
Используя C++, у вас есть два списка чисел. Числа в первом списке упорядочены по неубыванию. Для каждого числа во втором списке определите номера первого и последнего вхождения этого числа в первом списке. Решение можете включать использование стандартных функций. Задание содержит входные данные: два числа N и M (1≤N,M≤20000), затем N упорядоченных целых чисел первого списка, и далее M целых неотрицательных чисел второго списка. Все числа - 32-битные знаковые целые числа.

Рекомендуется сохранять верные ответы и всегда делиться с друзьями, ведь они могут тебе ещё пригодиться!

Telegram Whatsapp ВКонтакте
Морской_Корабль
25
Хорошо, давайте решим данную задачу.

1. Сначала создадим два вектора для хранения чисел из первого и второго списка:

cpp

#include 

#include 

#include 



int main() {

    int N, M;

    std::cin >> N >> M;



    std::vector firstList(N);

    for (int i = 0; i < N; ++i) {

        std::cin >> firstList[i];

    }



    std::vector secondList(M);

    for (int i = 0; i < M; ++i) {

        std::cin >> secondList[i];

    }

    

    // Здесь будет следующий шаг

    return 0;

}


2. Теперь создадим цикл для каждого числа во втором списке, чтобы определить номера первого и последнего вхождения в первом списке:

cpp

for (int i = 0; i < M; ++i) {

    int num = secondList[i];



    auto firstOccurrence = std::lower_bound(firstList.begin(), firstList.end(), num);

    auto lastOccurrence = std::upper_bound(firstList.begin(), firstList.end(), num);



    int firstIndex = (firstOccurrence != firstList.end()) ? (firstOccurrence - firstList.begin()) : -1;

    int lastIndex = (lastOccurrence != firstList.end()) ? (lastOccurrence - firstList.begin() - 1) : -1;



    std::cout << firstIndex << " " << lastIndex << "\n";

}


3. Итоговый код для вашей задачи:

cpp

#include 

#include 

#include 



int main() {

    int N, M;

    std::cin >> N >> M;



    std::vector firstList(N);

    for (int i = 0; i < N; ++i) {

        std::cin >> firstList[i];

    }



    std::vector secondList(M);

    for (int i = 0; i < M; ++i) {

        std::cin >> secondList[i];

    }



    for (int i = 0; i < M; ++i) {

        int num = secondList[i];



        auto firstOccurrence = std::lower_bound(firstList.begin(), firstList.end(), num);

        auto lastOccurrence = std::upper_bound(firstList.begin(), firstList.end(), num);



        int firstIndex = (firstOccurrence != firstList.end()) ? (firstOccurrence - firstList.begin()) : -1;

        int lastIndex = (lastOccurrence != firstList.end()) ? (lastOccurrence - firstList.begin() - 1) : -1;



        std::cout << firstIndex << " " << lastIndex << "\n";

    }



    return 0;

}


Этот код позволит определить номера первого и последнего вхождения каждого числа из второго списка в первом упорядоченном списке.