Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/104: Рейтинг темы: голосов - 104, средняя оценка - 4.64
34 / 34 / 21
Регистрация: 02.02.2012
Сообщений: 181
1

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

29.06.2013, 10:51. Показов 20454. Ответов 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;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.06.2013, 10:51
Ответы с готовыми решениями:

Найти в строке way левый слеш и заменить его на правый
Есть код, нужно найти в строке way левый слеш и заменить его на правый) void main() { string...

Реализация дерева левый сын, правый брат (указатели)
Задание такое:

Поменять местами левый и правый байты целого аргумента
разработайте макрос swab(х) который меняет местами левый и правый байты целого аргумента х...

Совершить в бинарном дереве обход Правый - Корень - Левый
Нужно совершить обход Правый корень левый в бинарном дереве. #include &quot;stdafx.h&quot; #include...

1
36 / 36 / 2
Регистрация: 28.04.2013
Сообщений: 110
29.06.2013, 16:54 2
lower_bound()
и
upper_bound()

Вам в помощь. Один ищет первое вхождение, второй последнее вхождение элемента в контейнер
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.06.2013, 16:54

Найти левый и правый крайние отрицательные элементы в массиве из 20 элементов
Помогите решить проблему. Есть задание &quot;Создать целочисленный массив из 20 элементов.Заполнить его...

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

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

Левый и правый блок
Пишу главную страницу сайта. Возникла проблема. Я сделал две колонки через float, одну левую,...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru