To solve this problem, we can adopt the Shortest Job First (combined with lexicographical order) strategy. The specific problem-solving approach is as follows:
1. Problem Analysis
To minimize the average waiting time, we need to prioritize those with shorter call times—because each person’s waiting time is the sum of the call times of all the people in front of them. By processing those with shorter call times first, we can significantly reduce the cumulative waiting time for subsequent individuals. In cases where call times are the same, we must ensure the lexicographically smallest order (i.e., prioritize those with smaller original IDs).
2. Core Idea
- Sorting Rule: Arrange all individuals in ascending order of call time; if call times are the same, arrange by original ID in ascending order (to ensure the lexicographically smallest order).
- Waiting Time Calculation: After sorting, the waiting time for the first person is 0; the waiting time for the second person is the call time of the first person; the waiting time for the third person is the sum of the call times of the first two individuals… and so on. After accumulating all waiting times, divide by the number of individuals to obtain the average waiting time.
3. Step Breakdown
- Data Structure: Define a structure
<span>Person</span>that includes each person’s original ID (id) and call time (time). - Sorting: Define a custom sorting rule
<span>cmp</span>, first sorting by<span>time</span>in ascending order, then by<span>id</span>in ascending order. - Calculate Total Waiting Time: Traverse the sorted queue, accumulating each person’s waiting time (i.e., the sum of the call times of all individuals in front).
- Output: First output the sorted original ID sequence, then output the average waiting time rounded to two decimal places.
4. Code Logic Correspondence
- The structure
<span>Person</span>stores each person’s ID and call time. - The sorting function
<span>cmp</span>implements the rule of “shorter time first, and if times are the same, smaller ID first.” - Traverse the sorted queue to calculate the total waiting time
<span>total_wait</span>, and finally calculate and output the average waiting time (rounded to two decimal places).
This strategy ensures the shortest average waiting time while satisfying the constraint of being the “lexicographically smallest” order, making it the optimal solution to this problem.
After reading the analysis, doesn’t it seem quite easy to implement? The reasoning is straightforward; try doing it yourself first, then look at the code!
