Интересно как решается эта задача. Спасибо.
Интересно как решается эта задача. Спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3757 |
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 | 171 |
2 | awoo | 165 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | maroonrk | 155 |
6 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 145 |
9 | pajenegod | 145 |
Название |
---|
Очевидным жадником вначале избавимся от всех с положительной прибавкой к авторитету. Далее требуется придумать некий порядок людей, в котором их выгодно выкидывать. Это то ли сумма, то ли разность a и b, точно не помню, доказывается методом "если они отсортированы в оптимальном ответе не так, докажем, что можно каких-то двух поменять, не ухудшить ответ и уменьшить количество инверсий".
После этого надо пустить динамику: текущий человек и текущий остаток авторитета, возвращается лучший ответ, два перехода. Получается много состояний, чтобы уменьшить их количество, надо поменять местами результат и один из параметров.
Была точно такая же задача "Яма" на ROI. В яме были участники с определённым ростом и длиной рук (могут ухватиться за край ямы), требовалось достать как можно больше.
Ага, причем задача за N*log(N) решается при желании.
Надеюсь, задача не с какого-то действующего контеста?
Для начала, кэп, что из тех, у кого b >= 0, можно выбирать любого подходящего участника и агитировать его. Дальше, у нас остались только те, у кого b < 0 (остальные с b >= 0 недостижимы и отбрасываются). Их, видимо, надо выбирать в порядке уменьшения a+b.
Cпасибо, пытаюсь писать решение. Задача не из какого-то действующего контеста :)
UPD:Сделал как сказал yeputons , менял местами результат и рейтинг. Вот код !!!