Hello all,
I’m stuck at this problem for 2 days now.
http://codeforces.com/problemset/problem/457/C
Tag says ternary search, which i looked for. But i’m not able to come up with the function on which we will apply ternary search to check.
Any help is appreciated.
Thanks and Regards.
Ok. First function returns how many money we should spend to make every candidate (except the guy) have less than k votes.
Second function is : if we have made all other candidates have less than k votes optimally, how many we should spend to make our guy the winner (to make him have k or more votes).
First is increasing, second is decreasing.
Sum of these functions is the result for some k.
So you can just ternary-search on the result.
please mark it as closed