Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
#1

Левый и правый двоичный поиск - C++

29.06.2013, 10:51. Просмотров 2613. Ответов 1
Метки нет (Все метки)

Помогите, пожалуйста, не проходит 1 тест, не понимаю из-за чего

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

Формат входных данных
В первой строке входных данных записано два числа N и M (1NM20000). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Примеры
входные данные10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
выходные данные
10 10
3 4
7 7
1 2
0

Вот моё решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
 
using namespace std;
 
int main()
{
    long n, k, m;
    cin >> n >> k;
    long *a = new long[n];
    long *b = new long[k];  
 
    for (long i = 0; i < n; i++)
        cin >> a[i];
 
    for (long i = 0; i < k; i++)
        cin >> b[i];
 
    for (long i = 0; i < k; i++)
    {
        int l = 0, r = n - 1;
        while (l < r)
        {
            m = (l + r) / 2;
            if (a[m] < b[i]) l = m + 1;
            else r = m;
        }
        if (a[r] == b[i])
        {
            cout << ++r << " ";
            while (a[r] == b[i])
                r++;
            cout << r << endl;
        }
        else cout << 0 << endl;
    }
 
    delete [] a;
    delete [] b;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2013, 10:51     Левый и правый двоичный поиск
Посмотрите здесь:
Найти в строке way левый слеш и заменить его на правый C++
C++ Поменять местами левый и правый байты целого аргумента
C++ Совершить в бинарном дереве обход Правый - Корень - Левый
Найти левый и правый крайние отрицательные элементы в массиве из 20 элементов C++
Написать программу которая при нажатии клавиш:правый Shift+ правый Alt блокировала бы клавишу 9 на клавиатуре. C++
Двоичный поиск C++
Двоичный поиск C++
двоичный поиск C++
Двоичный поиск C++
двоичный поиск C++
Двоичный поиск C++
Двоичный(бинарный) поиск C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
29.06.2013, 16:54     Левый и правый двоичный поиск #2
lower_bound()
и
upper_bound()

Вам в помощь. Один ищет первое вхождение, второй последнее вхождение элемента в контейнер
Yandex
Объявления
29.06.2013, 16:54     Левый и правый двоичный поиск
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru