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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@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

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

Решение