We can solve this by building an x-y coordinate, where the horizonal coordinate denotes the time and the vertical one denotes the quantity that we have downloaded or watched. One can simply draw two lines to describe the “download behavior” and “watch behavior”. We should find out the minimum t so that the “download behavior” line is always above the other line.
A straightforward implementation problem.
The main framework is to adopt a “stack” to match every “try” with the correct “match” (just like the classical “bracket matching problem”). Then, we find out the “nearest” try-catch pair that has the same “exception name”. Be careful of the processing of string parsing.
First note that we can omit any y = kx + b with k = 0, as they have no effect on the result (they just move the whole polyline in the vertical direction). Then, we deal with each function according to the sign of k, i.e., we divide them into two types, one containing positive k while the other containing negative k.
Next, we implement a “duplicate elements removing” operation, for positive k and negative k, respectively. Suppose that we have two functions y = k1x + b1 and y = k2x + b2, and they satisfy k2 = c × k1, b2 = c × b1, where c is a positive constant. This means that these two functions have the same “turning point”, and we can add them together to form a new single function y = (k1 + k2)x + (b1 + b2) while having no effect on the final result.
After the above operations, we can count the number of different “turning points”, and this is just the final answer.
The main idea is disjoint set union (dsu), with path compression (I am not sure of this name, but the target is to avoid the degradation from a tree to a single link with quite large depth). One can search this on the internet.
For this problem, we should also maintain an extra array to store the distance from some node u to its current root node v. One can check the codes shown in the tutorials.
Комментарии (0)
