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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.59
ann-joker
Сообщений: n/a
#1

Приближенный двоичный поиск - C++

03.07.2013, 20:17. Просмотров 2918. Ответов 2
Метки нет (Все метки)

Доброго времени суток, форумчане.

Задача такая: В первой строке входных данных содержатся числа N и K (0 > N,K >100001 ). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2*10^9. Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Вот мое решение задачи.
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
#include <iostream>
#include <cmath>
using namespace std;
 
int closest (int a[], int k, int n){
    int razn = 1000000;
    int ans = -1;
    for (int i = 0; i < n; i++){
        if (abs(a[i] - k)  < razn){
            razn = abs(a[i] - k);
            ans = a[i];
        }
    }
    return ans;
}
 
int main(){
    int n, k, a[100001], b[100001];
    cin >> n;
    cin >>k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
        
    
    for (int i = 0; i < k; i++)
        cin >> b[i];
 
    for (int i = 0; i < k; i++){
        cout << closest(a, b[i], n) << endl;
    }
    return 0;
}
Некоторые тесты проходит легко, однако, многие проваливает. А в некоторых превышено время. Может, неправильный ответ иногда связан с условием вывода меньшего из двух приближенных чисел. Как это можно исправить?
И насчет упрощения, чтобы работало быстрее нет идей.

Благодарю за помощь.

Добавлено через 2 часа 8 минут
Прошу помочь
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2013, 20:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Приближенный двоичный поиск (C++):

Приближенный бинарный поиск - C++
Реализуйте алгоритм приближенного бинарного поиска. Входные данные В первой строке входных данных содержатся числа N и K. Во второй...

Двоичный поиск - C++
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами методом двоичного поиска.. #include &lt;iostream.h&gt; ...

двоичный поиск - C++
Помогите, пожалуйста, модифицировать программу на рисунке, чтобы для выполнения двоичного поиска в массиве можно было использовать...

Двоичный поиск - C++
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int...

Двоичный поиск - C++
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды. #include &lt;stdafx.h&gt; #define N 10 ...

двоичный поиск - C++
Подскажите, пожалуйста, в вопросе: Какое дополнительное требование к массиву может быть применено при двоичном поиске, что бы определить...

2
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.07.2013, 22:53 #2
ann-joker, rofl ! у вас не двоичный поиск, а линейный ! У вас прога срабатывает за О(N*K), а требуется O(K * LogN) !

Добавлено через 1 минуту
Цитата Сообщение от ann-joker Посмотреть сообщение
N и K (0 > N,K >100001 )
тут наверное вот так:
0 < N, K < 100001

Набросал вот. Надеюсь, что правильно.
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
#include <iostream>
#include <cmath>
 
using namespace std;
 
int n;
int a[100002];
 
int closest(int c) {
    int l = 0, r = n - 1;
    for (int i = 0; i < 100; ++i) {
        int mid = (r + l) / 2;
        if (a[mid] > c)
            r = mid;
        else
            l = mid;
    }
    if (l != r)
        return (abs(a[r] - c) < abs(a[l] - c) ? r : l);
    return l;
}
 
int main() {
    int k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0, c; i < k; ++i)
        scanf("%d", &c), printf("%d ", a[closest(c)]);
    return 0;
}
1
ann-joker
Сообщений: n/a
09.07.2013, 08:49 #3
Ternsip, хм, поняла ошибку. Невнимательность, как обычно, меня подвела.
Все работает правильно. Огромное спасибо!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 08:49
Привет! Вот еще темы с ответами:

Двоичный поиск - C++
Нашел на форуме двоичный поиск, не подскажите как нужно изменить код, что бы программа выводила еще и индекс, в котором находится введенное...

Нерекурсивный двоичный поиск - C++
необходимо написать на С++ двоичный поиск в рекурсивном варианте. вот пример рекурсивной ф-ции двоичного поиска: int BinSerch(int...

Двоичный поиск в map - C++
Здравствуйте. Помогите разобраться в следующей проблеме. В общем, мне нужно реализовать двоичный поиск в map по ключам. Понятное дело,...

Двоичный (бинарный) поиск - C++
Вот такой вот вопрос: Есть например такой линейный массив 1 1 1 1 2 3 4 5 6 Вводят какое-то число и нужно проверить сколько...


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

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

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