Hi guys, i have 2 vector needed merge. How can I find min dictionary order of vector after merge.
ex : A = {2, 3} B = {4, 5}
one of satis way is : {2, 4, 5, 3}, opposite {3, 2, 4, 5}, {3, 2, 5, 4} is not.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | atcoder_official | 149 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | cry | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.07.2024 23:32:45 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
if you mean a queue , then it is mergesort isn't it
No in this case the vectors are sorted but they may not be. I think what he is asking is the lexicographically smallest merging where the relative order of each element from each vector doesn't change. Eg:- a = {5, 1}, b = {2, 6} the answer is {2, 5, 1, 6}
But wouldn't $$$[2,3]$$$ and $$$[4,5]$$$ result in $$$[2,3,4,5]$$$ then? I think OP needs to clarify this
yes, for sure. I was also confused on this, but he/she says "one of satis way is ..." hard to decode tbh :)
{2, 3, 4, 5} is the answer we need :v
The way to solve this is:
Think of the vectors as queues, and greedily pop from the queue with smaller front value.
But how to handle duplicates?
a concat ba concat bin O(1) which will tell us which queue to pop fromthank u, is it O(n)
bonus : {2, 3, 4, 5} is the answer of ex test cases
then maybe just do a greedy thing like having the tops out and compare and choose
how about hashing and binary search :v
Well, maybe binary search could work, but it doesn't make the solution any easier. There is a greedy two-pointers way to solve this problem in $$$O(n+m)$$$.
but when a[i] = b[j], which element should we get
advance both pointers until the two pointers point to a different character. choose the lexicographically smaller side (segment).
ex) assume we have two strings $$$\text{bbbbabbbbb}$$$ and $$$\text{bbbbcbbbbb}$$$. Now the first difference happens on $$$\text{a}$$$ and $$$\text{c}$$$, so you can append $$$\text{bbbba}$$$ to the answer, move the pointer on $$$\text{bbbbcbbbbb}$$$ to the previous position, and keep going. answer will be $$$\text{bbbbabbbbbbbbbcbbbbb}$$$.
tks u, it look like hash but complex O(n)
Is it SPOJ MINSEQ?