Given array A of size n we have to create an array B by re-arranging array A. Now we need to maximize the sum $$$|A_i - B_i|$$$. I think sorting A in increasing and B in decreasing order then adding corresponding element will result in optimal solution. Is this correct or there can be a better algorithm for this problem. Thanks in advance.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | cry | 160 |
| 2 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | atcoder_official | 158 |
| 5 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 149 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/24/2024 00:28:20 (j2).
Desktop version, switch to mobile version.
Supported by
yes, that's correct
There is a better algorythm in terms of complexity, since sorting is somewhat more than has to be done. We can also pair the elements by partitioning the array into two halfs, the upper one, and the lower one. And then pair any two elements from both halfs.
We can use nth_element() which works somewhat faster than sort().