← 返回 amazon 的题目列表Possible Survivors in Competitive Inventory Processes
类型:online_judge
In Amazon's expansive distribution network, there are n unique inventory processes, each supported by robots[i] robots. These processes are competitive, resulting in clash events every minute between two randomly chosen processes. During a clash:
The process with more robots overtakes the one with fewer robots, gaining its robots.
If both processes have the same number of robots, one process randomly wins and gains the other's robots.
This process repeats until only one inventory process remains. The task is to identify which inventory processes have a possibility of surviving until the end in at least one scenario. Return the indices of these processes (in ascending order, 1-indexed) that could potentially emerge as the last surviving process.
Example
n = 5
robots = [1, 6, 2, 7, 2]
Assuming 1-based indexing of the robots array:
The inventory process at index 2 may survive after the following clashes:
The 2nd process acquires the 1st process, gaining its robots and increasing its total to 6 + 1 = 7. Hence, robots = [0, 7, 2, 7, 2].
It then eliminates the 3rd process, raising its total count of robots to 9. Hence, robots = [0, 9, 0, 7, 2].
Next, it defeats the 4th process, enhancing its total count of robots to 16. Hence, robots = [0, 16, 0, 0, 2].
Finally, it conquers the 5th process, increasing its total robots to 18. Hence, robots = [0, 18, 0, 0, 0].
The inventory process at index 4 can also survive as follows:
Initially, the 4th process acquires the 1st process, inheriting its robots to total 8. Hence, robots = [0, 6, 2, 8, 2].
Next, it surpasses the 3rd process, raising its total to 10. Hence, robots = [0, 6, 0, 10, 2].
It then defeats the 2nd process, raising its total robots to 16. Hence, robots = [0, 0, 0, 16, 2].
Finally, it overcomes the 5th process, raising its total robots to 18. Hence, robots = [0, 0, 0, 18, 0].
Thus, both these inventory processes could continue to operate following the clashes. Other processes will be terminated at some point in all possible scenarios.
Function Description
Complete the function fetchProcessIndices with the following parameter(s):
int robots[n]: an array of integers representing the number of robots each inventory process controls.
Returns:
int[]: the identifiers of inventory processes in ascending order that could endure, post clashes in at least one probable scenario.
Constraints
1 <= n <= 2 * 10^5
1 <= robots[i] <= 10^9
Example
Input
5
1 6 2 7 2