Приближённый двоичный поиск

@Eisenstein · Регистрация: 28.06.2021

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

Для каждого из K чисел найдите ближайшее к нему число в отсортированном массиве.

Входные данные
В первой строке входных данных содержатся числа N и K (0<N,K<100001). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке — K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2⋅109.

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

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

Вывод
1
3
7
1
5

Он просто не работает, а что надо исправить, я не знаю

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
#include <iostream>
using namespace std;
 
int main() {
    int n, k, M;
    cin >> n >> k;
    int* s = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    int* g = new int[k];
    for (int i = 0; i < k; i++) {
        cin >> g[i];
        int L = 0;
        int R = n - 1;
        while (R - L > 1) 
        {
            M = (R + L) / 2;
            if (s[M] < i) 
            {
            L = M;
            }
            else 
            {
            R = M;
            }
        }
            if (i - s[L] <= s[R] - i) {
                cout << s[L] << endl;
            }
            else {
                cout << s[R] << endl;
            }
        
    }
 
}

@LegionK · 22.07.2021, 09:47

Кликните здесь для просмотра всего текста

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
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int bs(vector<int>&v,int k){
 
    int l = 0;
    int r = v.size();
 
    while(l+1 < r){
 
        int m = (l+r)/2;
 
        if(v[m] <= k)l = m;
        else r = m;
 
    }
 
    return v[l];
}
 
int main()
{
    int n,q;
    cin >> n >> q;
 
    vector<int>a(n);
    for(int i = 0;i<n;++i)cin >> a[i];
 
    for(int i = 0;i<q;++i){
 
        int t;
        cin >> t;
 
        cout << bs(a,t) << "\n";
 
    }
 
 
 
 
 
    return 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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    int n,q;
    cin >> n >> q;
 
    vector<int>a(n);
    for(int i = 0;i<n;++i)cin >> a[i];
 
    for(int i = 0;i<q;++i){
 
        int t;
        cin >> t;
 
        auto it = lower_bound(a.begin(),a.end(),t);
 
        if((it != a.begin()) && (*it > t))--it;
 
        cout << *it << "\n";
 
 
    }
 
 
 
 
 
    return 0;
}

Добавлено через 25 минут
Я неправильно задачу понял, извиняюсь. Два кода выше не работают.

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

Кликните здесь для просмотра всего текста

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
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main()
{
    int n,q;
    cin >> n >> q;
 
    vector<int>a(n);
    for(int i = 0;i<n;++i)cin >> a[i];
 
    for(int i = 0;i<q;++i){
 
        int t;
        cin >> t;
 
        int k = lower_bound(a.begin(),a.end(),t) - a.begin();
 
        if(k)--k;
 
        vector<int>diff;
 
        if(k-1 >= 0)diff.push_back(a[k-1]);
        diff.push_back(a[k]);
        if(k+1 < n)diff.push_back(a[k+1]);
 
        int mi = 1e9;
        int ind = 0;
 
        for(int j = 0;j<diff.size();++j){
 
            if(abs(t-diff[j]) < mi){
 
                mi = abs(t-diff[j]);
 
                ind = j;
            }
        }
 
        cout << diff[ind] << "\n";
 
    }
 
 
 
 
 
    return 0;
}

вот этот должен работать.

@Eisenstein · 22.07.2021, 13:47 **[ТС]**

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

вот этот должен работать

Странно, но он не работает. Ответ выдаёт верный, но тестирующая программа пишет, что нет

@dmitrii2000 · 22.07.2021, 13:58

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;
}

@LegionK · 22.07.2021, 14:25

Eisenstein, А, да, забыл минимальное значение mi поменять.

Кликните здесь для просмотра всего текста

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
#define ll long long
 
int main()
{
    ll n,q;
    cin >> n >> q;
 
    vector<ll>a(n);
    for(ll i = 0;i<n;++i)cin >> a[i];
 
    for(ll i = 0;i<q;++i){
 
        ll t;
        cin >> t;
 
        ll k = lower_bound(a.begin(),a.end(),t) - a.begin();
 
        if(k)--k;
 
        vector<ll>diff;
 
        if(k-1 >= 0)diff.push_back(a[k-1]);
        diff.push_back(a[k]);
        if(k+1 < n)diff.push_back(a[k+1]);
 
        ll mi = 1e10;
        ll ind = 0;
 
        for(ll j = 0;j<diff.size();++j){
 
            if(abs(t-diff[j]) < mi){
 
                mi = abs(t-diff[j]);
 
                ind = j;
            }
        }
 
        cout << diff[ind] << "\n";
 
    }
 
 
 
 
 
    return 0;
}

Вот так попробуйте. Если и это не получится, то я и не знаю в чем проблема.

@Eisenstein · 22.07.2021, 14:38 **[ТС]**

LegionK, что обозначает 1e10? Это как степень 10¹⁰?

@LegionK · 22.07.2021, 14:41

Eisenstein, Да, так степени десяти удобно писать. 1е5 = 10^5, 2e5 = 2*(10^5), 3e10 = 3*(10^10) и т.д.

Работает? Да/нет?

@Eisenstein · 22.07.2021, 14:44 **[ТС]**

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

Работает? Да/нет?

Да, работает. Спасибо ещё раз большое

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Eisenstein 2 / 2 / 0 Регистрация: 28.06.2021 Сообщений: 35 Записей в блоге: 1
	22.07.2021, 14:38 [ТС]
	LegionK, что обозначает 1e10? Это как степень 10¹⁰? 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	22.07.2021, 14:41
	Eisenstein, Да, так степени десяти удобно писать. 1е5 = 10^5, 2e5 = 2(10^5), 3e10 = 3(10^10) и т.д. Работает? Да/нет? 0

Приближённый двоичный поиск

Решение