|
Вернуться
| 1 Неизвестный, 21 июня 2018 г. 14:29:30 | |
|
Мне просто очень интересно решать задачи посложнее,так как я с Украины и еще только перешёл в 10 клас, а хочу выступить хорошо на районной и обласной олимпиадах,у меня есть опыт програмирования на паскале, но недавно поставил себе за цель взять призовое место на обласной олимпиаде, а мне стает не по себе когда заходять ни в чём не бывало люди и решают те же задачи которые я спрашывал только на другом языке. Етот сайт называется algotester, на нём я на 15 месте в рейтингу. Я думаю что мне уже стоит решать задачи по сложнее чем вы сказали, для меня не важно место, для меня важно качество и навыки которые я могу получить общаясь с вами, я буду и дальше развиватся в етом направлении. Благодарю за ваш отклик.
|
|
|
| 2 Меньшиков Фёдор Владимирович, 21 июня 2018 г. 13:53:47 | |
|
Ответом может быть число от min(A[i])+min(B[j]) до max(A[i])+max(B[j]). Вот по этому диапазону нужно делать двоичный поиск. И смотреть, сколько пар у нас меньше или равны этому числу. Сколько пар меньше или равны можно за O(n+m) найти двумя указателями. А расскажите пожалуйста ещё, откуда Вы эти задачи берёте. И почему Вам важно именно эти задачи решить. А то судя по Вашим вопросам они слишком сложны для Вас. А вот на acmp, где Вы по непонятной причине спрашиваете совета, есть архив, где много задач попроще, и где Вы можете прокачать свои навыки, решая более простые задачи. А потом уже и сложные задачи вроде тех что Вы спрашиваете решать. В терминах acmp сложность того, что Вы спрашиваете - 40-60%. Порешайте сначала задачи сложности 20-30%, потом потихоньку поднимайте сложность.
|
|
|
| 3 Неизвестный, 21 июня 2018 г. 12:40:10 | |
|
Я не очень понял ето:далее двоичный поиск по ответу,у нас же есть только k,нам суммы не даны об'ясните еще немного подробнее.Я знаю что есть nth_element в библиотеке algorithm она как раз находит k-тую порядковою статистику, но если я так делаю у меня лимит памяти едёт,я думаю ето изза того что ищу все сумы.
|
|
|
| 4 Меньшиков Фёдор Владимирович, 21 июня 2018 г. 8:14:14 | |
|
Заранее отсортировать A и B, далее двоичный поиск по ответу, при фиксированном ответе смотрим, сколько пар будет меньше или равно. При отсортированных A и B можно найти двумя указателями.
|
|
|
| 5 Неизвестный, 18 июня 2018 г. 19:20:41 | |
Как найти k-тую по величине(ето по моему называется k-тая порядковая статистика) суму пар двух масивов, А и B. Наведу пример:Пусть A.size()=3, а елементы : 2 3 4 , B.size()=3, а елементы :1 2 3
1<=A.size(),B.size()<=200000
-10^9<=A[i],B[i]<=10^9
1<=k<=n*m
Лимит часу 3 секунды, 256 МБ память
Находим все сумы пар етих масивов:
2+1=3, 2+2=4, 2+3=5, 3+1=4, 3+2=5, 3+3=6, 4+1=5, 4+2=6, 4+3=7,У нас получился масив:3,4,5,4,5,6,5,6,7.Сортируем его,у нас получается:3,4,4,5,5,5,6,6,7.Допустим k=3,мы выводим 5.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| |
