Solution:
The whole idea:
- Sorts b while preserving b's original index.
- Count the number of available numbers for each $b_i$, and also count how many pending number of it. From these two values we can calculate a "number of redundancy".
- We find the smallest $b_i$ for which "number of redundancy" is 0.
- Find the j with the smallest original index among all $b_j$ from 0 to i. And assign the currently smallest available number to $b_j$.
- According to the allocation of 4, repeat #2 and subsequent steps until all numbers are allocated.
Details of the idea:
Let's start with #3 first.
Consider the number of numbers that can be assigned for each $b_i$.
For example, when $b=[3, 4, 7, 8]$, there are only 2 numbers that can be used for 3 and 4 which is 1 and 2. And there are 4 numbers that can be used for 7 and 8: 1, 2 , 5, 6.
It is not difficult to find that the two numbers that can be used by 3 and 4 must be assigned to 3 and 4, but not to 7 and 8. This is because 3 and 4 have two pending number, and 3 and 4 have exactly 2 numbers available.
Furthermore, we found that after the allocation of 3 and 4, there are only 2 usable numbers left for 7 and 8, but also only 2 pending numbers for 7 and 8 are left. (Initially there are 4 numbers that can be used for 7 and 8, and there are also 4 pending numbers).
Therefore, we can draw a conclusion: the allocation of small numbers will affect large numbers, and we should give priority to the smaller $b_i$ whose "number of redundancy" is 0.
For example $[3, 4, 7, 8]$, although the "number of redundancy" of 4 and 8 are both 0, but in #3, we prioritize 4 instead of 8.
Then we go back to #2.
We only need to consider how many $b_i$ that are smaller than itself is not allocated. So 3 actually only has 1 pending number, 4 has 2, 7 has 3, and 8 has 4.
In other words, 3 does not consider the situation of 4, and 7 does not consider the situation of 8.
Because if we change b to $[3, 5, 7, 8]$, 3 and 5 will not need to be processed in advance. So when calculating pending item, we only need to calculate how many $b_i$ are less than or equal to the current value.
Let's move on to #4.
We already know that 1 and 2 need to assign to 3 and 4. The next question is where to allocate 1. Obviously this depends on the original index which retained by #1.
We assign 1 to the smallest original index. That is, if the original 4 is in front of the 3, it is assigned to 4.
It should be noted here that after we have allocated 1, we cannot immediately allocate the remaining number (only 2 in this example). Because after an allocation, the "number of redundancy" of the remaining numbers may change.
For example, after 1 is allocated to 4, the "number of redundancy" of 3 changes from 1 to 0, because there are 2 numbers available for 3 but only 1 pending number originally. After 1 is allocated to 4, only 2 is left for 3.
This is more obvious in Example 6: $b=[8, 7, 4, 5]$ (after sorting $[4, 5, 7, 8]$). At the beginning, only the "number of redundancy" of 8 is 0, and then exactly 8 is the number with the smallest original index. But after 1 is allocated to 8, 2 cannot be allocated to the remaining number with the smallest original index(that is, 7), but to go back to #2 and process 4 and 5 in advance.
Full example:
Let's take sample 6 as an example: $b=[8, 7, 4, 5]$.
#1, we sort and keep the original index. We get $[(4: 2), (5: 3), (7: 1), (8: 0)]$.
#2, we calculate the current "number of redundancy". We get $[(4, 2, 2), (5, 3, 1), (7, 1, 1), (8, 0, 0)]$
For example, 5 has [1,2,3] a total of 3 number is available, minus 2 pending numbers, so there is 1 "number of redundancy".
#3，only one "number of redundancy" is 0: (8, 0, 0).
#4, among all the numbers before 8, the smallest original index is 8. So we assign 1 to 8.
Repeat #2, the "number of redundancy" after update is: $[(4, 2, 1), (5, 3, 0), (7, 1, 0)]$
Here, because 8 has been allocated, it is deleted. At the same time 1 is no longer available, so the remaining "number of redundancy" are all decremented by 1.
#3, at this time the "number of redundancy" of 5 and 7 are both 0. We choose the smaller 5 to continue processing.
#4, among all numbers before 5 (referring to 4 and 5, excluding 7), the smallest original index is 4. So we assign 2 to 4.
Repeat #2 to get $[(5, 3, 0), (7, 1, 0)]$
Here, only 3 is left for 5 to be allocated, and since 4 is deleted, the number of pending item for 5 also becomes 1. So the "number of redundancy" of 5 is still 0.
#3 and #4, assign 3 to 5.
Repeat #2, #3, #4, assign 6 to 7.
No solution case:
Obviously, at any time, once the "number of redundancy" is less than 0, there must be no solution.
Implementation:
Look at #4 first, its essence is to find the minimum value of the original index within the interval from "0" to "$i$ obtained by #3". We immediately thought that the segment tree maintains the minimum value of the original index of the range.
For #3, we only need to maintain the minimum value of the "number of redundancy" of the range, plus the binary search, find the smallest $i$ of the subscript so that the minimum value of the "number of redundancy" of the interval is 0. It can also be implement through the segment tree.
Then consider the case of deleting the allocated $b_i$.
Note that all the minimum values of range are maintained on the segment tree, so after the number is allocated, we can change the value of its original index and the "number of redundancy" to infinity. In this way, this $i$ will never appear in subsequent process.
Finally consider the effect of assigning a number x to $b_i$ on the "number of redundancy" of other $b_j$.
For $b_j$ that is larger than $b_i$ itself, it does not actually affect the "number of redundancy". Because these $b_j$ will reduce an available number and also reduce a pending number. (far right)
For $b_j$ smaller than x, it will not be affected. Because this value is impossible to assign to them. (far left)
So in essence only when $b_j$ is between x and $b_i$, the "number of redundancy" will be reduced by 1. Because the available number of $b_j$ is reduced by 1, but the pending number will not be reduced. (middle)
But this is actually an range modification. Therefore, it can still be implemented with a segment tree.
Therefore, the entire implementation is to use the segment tree to maintain the minimum value of the original index and the minimum value of the "number of redundancy" of the range, and then find out the target i of #3 and the position of x with binary search.
Code:
Java
C++
