This problem can be solved by direct implementation as it requires. The main issue involved is the generation of all permutations for some given sequence. As the problem guarantees that all the given integers are different, a simple recursive backtracing algorithm is sufficient. Completing this, we can count the number of integers that satisfy the conditions.
This is a very nice problem to practice binary search. Different from the conventional binary search based on index, this one has to deal with "float type", and thus the loop should be terminated by limiting the number of search.
We can directly search the required answer. During each search, we enumerate all the elements and calculate two results, denoted as E_out and E_in as follows. If the element is no less than the current answer, then we add the difference to E_out; otherwise we add the difference to E_in. Note that here the difference is always larger than or equal to 0. Then, we compare whether E_out*(1-k/100) is no less than E_in or not. If yes, it means that the answer for the next loop should be increased; otherwise it should be decreased.
This problem has given me a deeper understanding of DFS, or backtracing.
We should adopt an array FLOW[n] to denote the fuels that are currently stored at some node, and later these fuels will flow to other nodes. As we start at node 1, we can enumerate all the possible values of fuels that are initially stored at node 1. It is sufficient to begin with 0 and end with 26, since there are at most 5 edges going out from node 1, and each of them is at most 5. The enumeration should be immediately terminated once we have found a reasonable value, since the problem asks to find out the minimum flow.
The DFS function should handle three cases depicted as follows:
For some node i, all the nodes to which it directs have already been processed. Then, we check FLOW[i], and if FLOW[i]=0, we should call this DFS function again but start at node i+1;
For node n-1, all the nodes that it directs to have already been processed. We should immediately "return" and update the maximum cost;
For some node i, we enumerate all the possible fuels X that can flow to some other connected node j, while decreasing FLOW[i] by X and increasing FLOW[j] by X. Then, we call the DFS function for the next node. Remember that after the function returns, FLOW[i] and FLOW[j] should be changed back to their original values.
Although the complete binary tree will have about 2^30 nodes, only a small fraction of them will be used, since the number of queries is limited to 10^5. Thus, we should first use map<int ,int > to compress the indices of nodes that we are going to deal with. Then, the problem can be solved based on the following two steps:
1) Update: We use cost[n] to denote the number of electrons that node-n and all its child nodes currently contain. Whenever a node with some electrons X is added, we find out the path from this node to the root node, and add the same number of electrons to all the nodes involved in this path. In other words, cost[n]=cost[n]+X, cost[n/2]=cost[n/2]+X, cost[n/4]=cost[n/4]+X...
2) Calculate: When a query comes, we calculate the required result, denoted as ANS. If the decay occurs at the first leaf node, we will obtain a component which consists of node-1, node-3 and all the child nodes of node-3 (there are other components, but we first only focus on this one). If the decay occurs at the second leaf node, we will obtain the component consisting of node-1, node-3 and all the child nodes of node-3 again. Besides, it can be seen that if decay occurs at any leaf node with index from [1, 2^(h-1)], i.e., the first half leaf nodes, we will always obtain the component with node-1, node-3 and all the child nodes of node-3. Moreover, we can compute that this special component has a charge of cost[1]-cost[2], while for the other components, it will have charges of at most cost[2]. Therefore, if we have cost[2]<cost[1]-cost[2], it means that if decay occurs at the first half leaf nodes, it will always contribute to the final expectation with 2^(-1)*(cost[1]-cost[2]), i.e., ANS=ANS+2^(-1)*(cost[1]-cost[2]). Thus, we can skip the first half leaf nodes and consider the case that the decay occurs at the second half leaf nodes, i.e., we can move to node-3. On the other hand, if cost[2]>cost[1]-cost[2], it means that cost[3]<cost[1]-cost[3]. This can be proved by using
cost[1]-cost[3]=cost[2]+C(some constant)>cost[2]>cost[1]-cost[2]=cost[3]+C(some constant)>cost[3]
This implies that we can skip the second half leaf nodes, and ANS=ANS+2^(-1)*(cost[1]-cost[3]), and we can move to node-2.
In fact, the problem has been reduced to another one with height h-1, and we can thus repeat the above arguments again. Suppose that we are now at node-3, and thus we should compare cost[3] and cost[3]-cost[6]. However, remember that as we are at node-3 now, and thus the decay should occur at leaf nodes with indices from [2^(h-1)+1, 2^h]. This implies that we will always have a component which consists of node-1, node-2 and all the child nodes of node-2, with charge of cost[1]-cost[3]. We use another variable max_cost to denote this value, i.e., max_cost=cost[1]-cost[3]. This will affect the calculation of ANS. Suppose that cost[3]<cost[3]-cost[6], and then we should compute ANS=ANS+2^(-2)*max(max_cost, cost[3]-cost[6]) rather than directly adding cost[3]-cost[6] to ANS. After this, we should update max_cost=max(max_cost, cost[3]-cost[7]).
Комментарии (0)
