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 | 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 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | atcoder_official | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
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 :)