see this imageand then this image . why they are giving different outputs when i want the lower bound of 6?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
see this imageand then this image . why they are giving different outputs when i want the lower bound of 6?
Name |
---|
lower_bound or any other binary search function can only apply on sorted containers, so in the case of the first picture, try sorting the vector before calling lower_bound. in the second picture, you are calling lower_bound on a reverse sorted container (sorted from greater to smaller) which i think is going to find the first element which is smaller or equal to provided integer starting from the greatest element. you can think of it this way: usually, we store elements in the multiset or set as multiplied with -1 instead of using greater<>, then the set is going to be {-8, -7, -5, -5, -3} now instead of lower_bound(6) we call lower_bound(-6) which in this case is going to be -5 which is the first element greater or equal to -6, so the answer is -(-5) = 5.
now whenever you found yourself asking about the behavior of some class or function in c++, you can search for the name of the class on google and find some documentation, usually, they are more than enough, and it's even better to find some good documentation of standard containers and algorithm and study it all, as it will save a lot of try and error and maybe some wrong verdicts in contests.
good luck!
thanks a lot...but one thing i wanted to say..the image 1 has a sorted vector in non-increasing order. doesn't it count as sorted?
no, you can try lower_bound(vec.rbegin(), vec.rend()).