I was trying this problem for quite a while, but failed to come up with the correct solution. Maybe you guys can help me.
Problem link: http://main.edu.pl/en/archive/oi/2/sze
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 152 |
10 | maroonrk | 151 |
I was trying this problem for quite a while, but failed to come up with the correct solution. Maybe you guys can help me.
Problem link: http://main.edu.pl/en/archive/oi/2/sze
Name |
---|
Think about some job i, i+1. The total time to complete job i+1 (in order of [1 ... i-1] [i] [i+1]) is
T + aiT + bi + ai + 1(T + aiT + bi) + bi + 1
= (ai + 1 + 1)((ai + 1)T + bi) + bi + 1
when T = total time took to complete till job i-1
now think that we process in order of [1 ... i-1] [i+1] [i], then the total time is
(ai + 1)((ai + 1 + 1)T + bi + 1) + bi
Say ci = ai + 1. now, if this inequality holds, it's better to swap job i and i+1.
ci + 1ciT + ci + 1bi + bi + 1 > cici + 1T + cibi + 1 + bi
which is
ci + 1bi + bi + 1 > cibi + 1 + bi
now replace ci to ai, we get :
ai + 1bi > bi + 1ai
So, if above equality holds, we should swap i and i+1. This is essentially angular sort.
code : http://ideone.com/c70x8s
Thanks a lot. That's a really nice solution :)