Hi, Can anybody help me to figure out how to apply binary search for the problem 231C - To Add or Not to Add.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Hi, Can anybody help me to figure out how to apply binary search for the problem 231C - To Add or Not to Add.
Название |
---|
Why not to read editorial?
Referring to editorial was my first destination but ,I can't clearly get the idea. So if you could help me out , it'd be great.
Well. First part — second number in answer should be a number from initial array. It's explained good enough there. So, we need to check all the numbers from array and calculate, how many operations of "+1" we need to use — the first number for our answer depends on that. That's true, as much operations we use — so much equal numbers we can obtain. Consider the following forward algo: first, we take a[i-1] and apply "+1" to it until a[i-1]==a[i], then go to a[i-2] and so on: we apply more operations — we get more numbers. Hence, first part of answer is monotonic function, which depends on number of applied operations. And we can use binary search here. Let cnt be that number of operations... And then — last part of editorial as it is. Is it better now?
clear thinking. I think lama_codes will solve it.