HINT 1
HINT 2
HINT 3
HINT 1
HINT 2
HINT 3
HINT 4
HINT 1
HINT 2
5A. K-th Number in the Union of Segments
HINT 1
HINT 1
HINT 2
HINT 1
HINT 2
# | User | Rating |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | maroonrk | 155 |
6 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Binary Search EDU
Average should be in double not int or long long.
Any length is ok as long as the average is maximum.
Try a test case that all number is 0.
It is a DAG so we can use top sort + DP to get shortest path.
Binary search for the average, minus average on every edge.
If the shortest path is <= 0, it means we can have an even lower average. If the shortest path is > 0, it means this average is too high. Note, we don't need to find a path that is exactly 0 cost. Binary search will help us narrow down.
1 might not be the only source, so we need to push all in degree 0 to queue first.
(a+b)/(c+d) > m => a+b > (c+d)*m => a-m*c + b-m*d > 0
Binary search for m.
5A. K-th Number in the Union of Segments
Just follow what theory says
k should be 0 indexed for the theory, so [1, n^2] becomes [0, n^2-1]. Because cnt(x) could return 0, we need k to start from 0, otherwise 1 will be skipped.
There is a trick to get O(n) for cnt(x). Start from bottom left and count towards upper right, if mid > i*j, move j, otherwise move i.
k should be 0 indexed.
Sort both array and use two pointers method for cnt(x). Start from 0 of first array and start from n-1 of second array.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en2 | NaoJoeMiao | 2022-06-06 19:42:35 | 2080 | (published) | ||
en1 | NaoJoeMiao | 2022-06-06 07:58:23 | 413 | Initial revision (saved to drafts) |
Name |
---|