Бинарный поиск

@EVGENNIY1337 · Регистрация: 25.07.2018

Author24 — интернет-сервис помощи студентам

Никак не могу понять почему у меня не проходит тесты данный код.
Задача выглядит так:

Входные данные
В первой строке входных данных содержатся числа N и K (0NK100001). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109.

Выходные данные
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Примеры
входные данные
5 5
1 3 5 7 9
2 4 8 1 6
выходные данные
1
3
7
1
5

C++

#include <iostream>
#include <cmath>
 
using namespace std;
 
int masn[100000] = {};
 
int bin(int x, int L, int R)
{
    int left, right, m;
    left = L;
    right = R;
    if (x > masn[right - 1])
        return masn[right - 1];
    while (right - left > 1)
    {
        m = (right + left) / 2;
        if (masn[m] == x)
            return masn[m];
        if (masn[m] < x)
            left = m;
        else
            right = m;
    }
    return masn[right - 1];
}
 
int main()
{
    int a, b, mask[100000] = {};
    cin >> a >> b;
    for (int h = 0; h < a; ++h)
        cin >> masn[h];
    for (int h = 0; h < b; ++h)
        cin >> mask[h];
    int j = 0;
    while (j < b)
    {
        cout << bin(mask[j], 0, a) << endl;
        j++;
    }
    system("pause");
    return 0;
}

@Kuzia domovenok · 21.10.2018, 23:29

Сообщение от EVGENNIY1337

Никак не могу понять почему у меня не проходит тесты данный код.

потому что бинпоиск работает только в отсортированных массивах, а не в едва лишь введённом.

Добавлено через 8 минут
потому что находится не ближайшее число, а ближайшее слева число

Добавлено через 7 минут

C++

int bin(int x, int L, int R)
{
    int left, right, m;
    left = L;
    right = R;
    if (x > masn[right - 1])
        return masn[right - 1];
    while (right - left > 2)
    {
        m = (right + left) / 2;
        if (masn[m] == x)
            return masn[m];
        if (masn[m] < x)
            left = m;
        else
            right = m;
    }
    if (masn[right - 1] - x > x - masn[left])
        return masn[left];
    return masn[right - 1];
}

@EVGENNIY1337 · 22.10.2018, 14:28 **[ТС]**

вот вывод этого кода:
5 5
1 3 5 7 9
2 4 8 1 6
3
3
9
1
5
что не верно

@Kuzia domovenok · 22.10.2018, 14:41

смотрим в массиве 1 3 5 7 9 найти ближайшее к 2 число, если таких несколько - вывести левое
на запрос 2 ответ? может 1? нет, 3
на 4 - 3 верно
на 8 - 9 опять не так
на 1 - 1 и на 5-5 в этом сомнений и не было, сомнения в поиске ближайших слева чисел.

@EVGENNIY1337 · 22.10.2018, 15:08 **[ТС]**

Сообщение от EVGENNIY1337

наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

1 3 одинаково близки к 2, а меньшее из них - 1, но ваш код выводит 3

@Kuzia domovenok · 22.10.2018, 15:22

C++

int bin(int x, int L, int R)
{
    int left, right, m;
    left = L;
    right = R;
    if (x > masn[right - 1])
        return masn[right - 1];
    while (right - left > 2)
    {
        m = (right + left) / 2;
        if (masn[m] == x)
            return masn[m];
        if (masn[m] < x)
            left = m;
        else
            right = m;
    }
    if (masn[right - 1] - x >= x - masn[left])
        return masn[left];
    return masn[right - 1];
}

@EVGENNIY1337 · 22.10.2018, 15:26 **[ТС]**

ваш код выполняет ровно те же тесты, как и мой, только чуть медленнее, и не проходит все требуемые тесты

@Kuzia domovenok · 22.10.2018, 15:31

какие ещё нафиг тесты?

@EVGENNIY1337 · 22.10.2018, 15:53 **[ТС]**

в протоколе пишется:

Статистика
Параметр Значение Тест
Первый непройденный тест Неправильный ответ 2
Максимальное процессорное время 0.282 19
Максимальный расход памяти 2613248 19
Максимальное астрономическое время 0.285 19
Тест Статус Балл Время работы Астрономическое время работы Используемая память
1 OK 0 0.001 2199552
2 Неправильный ответ 0 0.001 2199552
3 Неправильный ответ 0 0.002 2199552
4 OK 0 0.001 2199552
5 OK 0 0.001 2199552
6 Неправильный ответ 0 0.001 2199552
7 OK 0.027 0.029 2199552
8 OK 0.026 0.027 2199552
9 OK 0.026 0.027 2199552
10 Неправильный ответ 0.027 0.029 2199552
11 Неправильный ответ 0.026 0.027 2199552
12 Неправильный ответ 0.026 0.027 2199552
13 Неправильный ответ 0.028 0.029 2199552
14 Неправильный ответ 0.027 0.028 2199552
15 Неправильный ответ 0.027 0.028 2199552
16 Неправильный ответ 0.029 0.03 2199552
17 Неправильный ответ 0.027 0.028 2199552
18 Неправильный ответ 0.272 0.274 2609152
19 Неправильный ответ 0.282 0.285 2613248
20 Неправильный ответ 0.277 0.28 2609152
21 Неправильный ответ 0.275 0.277 2609152
22 OK 0 0.001 2199552

@Kuzia domovenok · 22.10.2018, 16:22

C++

#include <iostream>
#include <cmath>
 
using namespace std;
 
int masn[100000] = {};
 
int bin(int x, int L, int R)
{
    int left, right, m;
    left = L;
    right = R;
    if (x > masn[right])
        return masn[right];
    while (right - left > 1)
    {
        m = (right + left) / 2;
        if (masn[m] == x)
            return masn[m];
        if (masn[m] < x)
            left = m;
        else
            right = m;
    }
    if (masn[right] - x >= x - masn[left])
        return masn[left];
    return masn[right];
}
int a, b, mask[100000] = {};
int main()
{
    cin >> a >> b;
    for (int h = 0; h < a; ++h)
        cin >> masn[h];
    for (int h = 0; h < b; ++h)
        cin >> mask[h];
    int j = 0;
    while (j < b)
    {
        cout << bin(mask[j], 0, a-1) << endl;
        j++;
    }
    return 0;
}

@EVGENNIY1337 · 22.10.2018, 16:31 **[ТС]**

спасибо

@EVGENNIY1337 0 / 0 / 0 Регистрация: 25.07.2018 Сообщений: 31
	22.10.2018, 14:28 [ТС]	3
	вот вывод этого кода: 5 5 1 3 5 7 9 2 4 8 1 6 3 3 9 1 5 что не верно 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,519 Записей в блоге: 1
	22.10.2018, 14:41	4
	смотрим в массиве 1 3 5 7 9 найти ближайшее к 2 число, если таких несколько - вывести левое на запрос 2 ответ? может 1? нет, 3 на 4 - 3 верно на 8 - 9 опять не так на 1 - 1 и на 5-5 в этом сомнений и не было, сомнения в поиске ближайших слева чисел. 0

@EVGENNIY1337 0 / 0 / 0 Регистрация: 25.07.2018 Сообщений: 31
	22.10.2018, 15:08 [ТС]	5
	Сообщение от EVGENNIY1337 наиболее близкое к данному. Если таких несколько, выведите меньшее из них. 1 3 одинаково близки к 2, а меньшее из них - 1, но ваш код выводит 3 0

@EVGENNIY1337 0 / 0 / 0 Регистрация: 25.07.2018 Сообщений: 31
	22.10.2018, 15:26 [ТС]	7
	ваш код выполняет ровно те же тесты, как и мой, только чуть медленнее, и не проходит все требуемые тесты 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,519 Записей в блоге: 1
	22.10.2018, 15:31	8
	какие ещё нафиг тесты? 0

@EVGENNIY1337 0 / 0 / 0 Регистрация: 25.07.2018 Сообщений: 31
	22.10.2018, 15:53 [ТС]	9
	в протоколе пишется: Статистика Параметр Значение Тест Первый непройденный тест Неправильный ответ 2 Максимальное процессорное время 0.282 19 Максимальный расход памяти 2613248 19 Максимальное астрономическое время 0.285 19 Тест Статус Балл Время работы Астрономическое время работы Используемая память 1 OK 0 0.001 2199552 2 Неправильный ответ 0 0.001 2199552 3 Неправильный ответ 0 0.002 2199552 4 OK 0 0.001 2199552 5 OK 0 0.001 2199552 6 Неправильный ответ 0 0.001 2199552 7 OK 0.027 0.029 2199552 8 OK 0.026 0.027 2199552 9 OK 0.026 0.027 2199552 10 Неправильный ответ 0.027 0.029 2199552 11 Неправильный ответ 0.026 0.027 2199552 12 Неправильный ответ 0.026 0.027 2199552 13 Неправильный ответ 0.028 0.029 2199552 14 Неправильный ответ 0.027 0.028 2199552 15 Неправильный ответ 0.027 0.028 2199552 16 Неправильный ответ 0.029 0.03 2199552 17 Неправильный ответ 0.027 0.028 2199552 18 Неправильный ответ 0.272 0.274 2609152 19 Неправильный ответ 0.282 0.285 2613248 20 Неправильный ответ 0.277 0.28 2609152 21 Неправильный ответ 0.275 0.277 2609152 22 OK 0 0.001 2199552 0

@EVGENNIY1337 0 / 0 / 0 Регистрация: 25.07.2018 Сообщений: 31
	22.10.2018, 16:31 [ТС]	11
	спасибо 0

Бинарный поиск

Решение