| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
how to solve this problem:
given a n — numbers of players and their height h_i. You need to split to k teams that the incompatibility is minimal. Incompatibility is the sum of the mx(maximum height of team player)-h_i(height of other player)
n <= 10^5
k <= min(n,20)
h_i <= 10^6
Please give sample input/output and its explanation to understand the problem better.
Give some example input and result (or a link to the original problem) cause I'm not sure if I understand the problem properly. This is my idea: 1) Sort all the players by their heights increasingly. We can assume that the best solution always put players with similar heights to one team (because it's optimal) so our problem is just to divide this sorted array into segments. If some players should be in one team, they're consecutive segment in the array. 2) Calculate prefix sums for the sorted array. It let us to count incompatibility of a given team in O(1) 3) Apply dynamic programming to two-dimensional array with n columns and k rows. The solution will be in left-down corner of the array. Complexity is O(k*n). I think it's enough as it needs at most 2*10^6 operations.