One should take care of the precision problem. We need an angle θ to “include” a circle with radius r, where 
. Thus, we can have 
small circles, which is 
. To avoid wrong answer caused by precision, we can implement x ≤ y + ε instrad of x ≤ y.
In fact, we only need fill a table, where the entry in row i and column j denotes the card that is given to the j-th person after the i-th card is obtained. A simple observation is that when the i-th card is obtained, we should first find out the one with the maximum preference, and denote its index as p. It is obvious that this card should be given to every person except for the one with index p. For him, we should give the card with the second maxumum preference. Thus, it is sufficient to find out the cards with the first and second maximum preference, and fill the table with them.
Moreover, we should also keep updating the best card that each person can obtain. To calculate this result, we should first convert the preference sequence of each person into a “rank” sequence, which tells the rank of each card in the preference sequence.
Once completing the above implementation, we can find out the answer for each person column by column. For each column, we can start from bottom to top, and once we find that the entry in the current row is equal to the best card, we can store the row index as the answer and immediately skip to the next column.
The optimal strategy is that we keep updating the number of different sizes, and always select the three balls that have the maximum numbers. Well, I did not figure out the proof...
The above idea can be simply implemented by using a priority queue. However, the data should be compressed in previous since the given range is too large.
I have learned a very neat and general method. For an array a[n], we first copy all the elements to another array b[n] as a backup. Then, we sort a[n] in an increasing order, and set m = unique(a, a + n) - a, after which m will be equal to the total number of unique elememts (“unique” can be found in STL of C++). Finally, we implement id = lower_bound(a, a + m, b[i]) for every b[i] (“lower_bound” also belongs to STL of C++). After the above steps, in fact we have already mapped b[i] to a smaller number id.
There exists a greedy solution.
We sort the given sequence in an increasing order. Then, we keep updating the prefix sum and the current problem can be successfully submitted as long as the corresponding prefix sum does not exceed 720. For each problem with a prefix sum that is not larger than 360, its penalty time is zero; otherwise, it contributes a penalty time which is equal to the difference between 360 and the corresponding prefix sum.
The greedy solution can be proved by a standard scheme, which can be found in many books.
Comments (0)
