How to solve the problem below in O(log2n) C++: You have the i'th element of an unsorted array. you have to find the nearest(absolute difference of the values is as small as possible) element of the i'th element from the right side.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.05.2024 20:02:57 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Impossible. You will spend at least O(n) to read everything and while you're reading you can just calc the answer.
If you're trying to solve for O(logn) per query. You can do binary search on set/sorted array etc.
I'm thinking about that too. but we can use set and lower_bound to complete the task.
if you mean right side of the sorted array then you can use a set and do lower_bound on that to give the element just greater than your current element.
if you mean right side of the unsorted array then you can iterate from right and find the nearest element in the set i guess something like that although i admit this approach seems like it might not be that simple.
P.S. do tell the approach when you find it, it seems interesting :)
maintain a set, iterate from n to 1. for each i, find the value closest to a[i] on set (can be done using lower_bound), then insert a[i] into set