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

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

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

Задача такая: В первой строке входных данных содержатся числа 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++
Двоичный поиск C++
C++ Двоичный (бинарный) поиск
двоичный поиск C++
двоичный поиск C++
Двоичный поиск C++
Приближенный бинарный поиск C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для 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;
}
ann-joker
Сообщений: n/a
09.07.2013, 08:49     Приближенный двоичный поиск #3
Ternsip, хм, поняла ошибку. Невнимательность, как обычно, меня подвела.
Все работает правильно. Огромное спасибо!
Yandex
Объявления
09.07.2013, 08:49     Приближенный двоичный поиск
Ответ Создать тему
Опции темы

Текущее время: 00:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru