Explanation of lower_bound function.

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:15:15
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя AHMADUL

Explanation of lower_bound function.

Автор AHMADUL, история, 5 лет назад, По-английски

I was trying to solve problem B1 of Helvetic Coding Contest 2019 online mirror (teams allowed, unrated). I got WA and TLE for a several time.Then I went to standings and found a line from a submission: int f=lower_bound(dg,dg+b,make_pair(a[i],10000000))-dg;
But,I couldn't understand it,,why I have to subtract dg at last??? Now, I am badly in need of help.Someone please explain the above statement.

-9

AHMADUL
5 лет назад
14

Комментарии (11)

Показать архивные | Написать комментарий?

Naim

5 лет назад, # |

lower bound returns first iterator of the value greater then or equal you are searching for. And by seeing your code it can be assumed it is used for finding the position of the value of make_pair(a[i], 10000000) in a container named dg. If you subtract dg from the returned iterator of lower_bound function then you will get the position. because dg is similar to dg.begin() here. both of them points first value of the container. [ extra tip: subtracting two iterator or pointer gives how many chunks of memory address are there between(not depends on your datatype) ]. you can know more about lower bound in here

btw, next time please attach the code where you have taken a part from it. Cause now I don't know whether the dg container is sorted or not. or which container is it. Thanks, have a good day. :D

→ Ответить

coyorkdow

5 лет назад, # ^ |

← Rev. 3 →

-7

dg is an array(not std::array but std::pair<int,int> dg[10]) but not a container. array shall not support begin() method, anyway it's not an obeject at all. and a container's name is also not equal to its begin() method. But since c++11 you can use std::begin() and std::end() whether arr is an array or a container.

→ Ответить

Naim

5 лет назад, # ^ |

coyorkdow i didn't know without a container we can store pairs. It would be nice of you if you give some reference about this. Thanks. :)

→ Ответить

coyorkdow

5 лет назад, # ^ |

← Rev. 2 →

In c++ containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like vector, queues, lists and stacks. reference from https://en.cppreference.com/w/cpp/container. So std::pair<int,int> is not a container but std::vector<std::pair<int,int>> is a container that stores std::pair<int,int>. Meanwhile std::pair<int,int>[100] and new std::pair<int,int>[100] can also stores pairs but neither are container. When memory are allocated, each object will call its default constructor.

→ Ответить

coyorkdow

5 лет назад, # |

← Rev. 2 →

lower_bound returns an iterator(or an pointer if parameters are not iterators) pointing to the first element in the range [first, last) that is not less than value you gived. So if you want to get the index of an element then you should transform it into an integer. Both random iterator and or pointer support subtract operation and will return the numbers of differences of elements between two interators or pointers(i.e. an iterator pointing to a[5] subtract to an interator pointing to a[2] will returns 3). Since dg is an array, array name points to the first element of the array. So after you do the subtract you get the index of the first element in the range from dg[0] to dg[b] which is not less then make_pair(a[i],10000000).

→ Ответить

riadwaw

5 лет назад, # ^ |

Pointer is a kind of iterator

→ Ответить

AHMADUL

5 лет назад, # ^ |

make_pair(a[i],10000000)--->What kind of argument is it???Why I have to write it in the third slot of the funtion???

→ Ответить

coyorkdow

5 лет назад, # ^ |

It is the "value you gived". std::make_pair() will return a pair which contains two parameters. If a[i] is an int value then you will get a std::pair<int,int> object. You find the first element that is not less than this pair.

→ Ответить