Sort the array in the required order, and find out all the terms that have exactly the same data as the k-th one.
In fact, we can keep inserting x into the array until we find that the median is equal to x.
Why this works? One can see that if the median is less than x, then we should insert more integers that are larger than x; otherwise we should insert more integers that are less than x. Nevertheless, x can be viewed as an integer that is both “less than” and “larger than” x itself.
It can be proved that it is definitely sufficient to insert at most n + 1 xs, and thus the complexity is N2log(N).
My codes have about 400 lines....
The basic idea is dp. We use dp[i][j] to denote the maximum profit we can obtain, when the j-th customer has made his decision (all the customers are sorted in an increasing order of their feet sizes l).
In details, i can take values 0, 1, 2, 3, which is in fact a bitmask. Note that when the j-th customer has feet size l[j] (we write l for short), he can buy shoes of size s = l and s = l + 1. We use 00 to denote that after the j-th customer has made his decision (he can buy one pair of shoes or nothing), shoes of size s = l and s = l + 1 are not sold, and use 01 to denote that after his decision, shoes of size s = l is not sold while that of size s = l + 1 is sold. Similarly, 10 denotes that after his decision, shoes of size s = l is sold while that of s = l + 1 is not sold. Finally, 11 denotes that both shoes of size s = l and s = l + 1 are sold.
Note that dp[i][j] only depends on dp[i][j - 1]. However, the recursicve formula should be deduced based on three cases.
1) l[j] = l[j - 1] + 1: for each state of dp[i][j - 1], i.e., 00, 01, 10, 11, the last bit denotes the shoes of the same size as that denoted by the first bit of states (also 00, 01, 10, 11) of dp[i][j]. This means that, for instance, 01 can not be transferred to states 00 and 01, since the shoes of size l[j] has been sold after the (j - 1)-th customer made his decision.
2) l[j] = l[j - 1]: the states of dp[i][j - 1] and dp[i][j] denote exactly the shoes of the same size. This means that, for instance, 01 can not be transferred to states 10 and 00 (similar reasons as above).
3) l[j] > l[j - 1] + 1: this means that the states of the j-th customer do not depend on those of dp[i][j - 1].
In case that the shoes of size l do not exist in the given input, we can still consider that this pair of shoes “exist” with zero cost.
We use fa[n], fb[n], fc[n] and fd[n] to denote the total number of ways to stay at nodes a, b, c and d after n steps, when we first start at node d. The recursive formula for each function is similar, and they all have forms of fa[n] = fb[n - 1] + fc[n - 1] + fd[n - 1]. Thus, we can adopt an array dp[4][n] to calculate and store all the results.
To further reduce the space complexity, note that dp[i][n] only depends on values of dp[j][n - 1], and thus it is sufficient to use dp[4][2] to store the values at the last step, and update values at the current step.
Comments (0)
