386B - Fly, freebies, fly! Please help me understand this solution. 5711342 Is this the two pointers method. Why is the final answer ans = max(ans,j-i)
?
№ | Пользователь | Рейтинг |
---|---|---|
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 | 166 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
386B - Fly, freebies, fly! Please help me understand this solution. 5711342 Is this the two pointers method. Why is the final answer ans = max(ans,j-i)
?
Название |
---|
Here
ans
will contain the maximum of previous result and new result.j-i
is the new result freebie can visit inT
seconds starting fromith
second.This solution is similar to be brute force. So the main idea of problem is to find maximum in sorted timings of
j-i
, wherea[i] + t <= a[j]
(i <= j
).for example, first lucky student was i-th. it means that some next students whose time is not greater than
a[i] + t
are lucky too. We can find this maximum by brute force in submission 5711342 and by two pointers method. e.g. 5705879. Difference is that we don't changej
, because if we know thata[i] + t <= a[j]
, this means thata[i + 1] + t <= a[j]
too.