| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Given two arrays A and B of size N. Let's take A={4,2,8} AND B={2,7,3}. All possible absolute values are 1: |4-2|+|4-7|+|4-3|=6 ; 2: |2-2|+|2-7|+|2-3|=6 ; 3: |8-2|+|8-7|+|8-3|=12; Sum of all these is 6+6+12=24;
Constraints : 1<=N<=10^5 , |Ai|,|Bi|<=10^6, so Ai,Bi can be negative
Any help with solution with time complexity O(nlogn)?
Auto comment: topic has been updated by Vasiljko (previous revision, new revision, compare).
Please problem link ?
It is on Serbian language but you can translate it. http://bubblebee.petlja.org/Media/Default/Problem/Drzavno%202015%20B1%20Apsolutno%20broj.pdf
We can first sort both arrays ----O(nlogn)
Now we can find in how pairs each element will be greater element(we add this many times ot the sum) and in how many it will be smaller one using binary search. We do this for all elements(we subtract this many times from sum) --O(nlogn)(we can even do two pointers --O(n))
Total = O(nlogn)
I thought of two pointers but couldn't implement it idk why, but binary search solution is not really clear to me. Can you post code? I would be really gratefull.
Oh i got it. Thank you so much <3 :)