Location>code7788 >text

Rock Valley P1223 Line up for water

Popularity：187 ℃/2024-08-05 17:46:27

P1223 Queuing for water

Title Description

there are\(n\) Individuals are lined up in front of a faucet to receive water, if the time for each individual to receive water is\(T_i\)Please program to find this\(n\) Individuals line up in an order such that\(n\) Individuals have the smallest average wait time.

input format

The first line is an integer\(n\)。

second line\(n\) The first integer, the second integer, the third integer, the first integer, the first integer, the first integer\(i\) integer (math.)\(T_i\) denote\(i\) Individual water pickup time\(T_i\)。

output format

The output file has two lines, the first line is a queuing order with the shortest average time; the second line is the average waiting time under this alignment scheme (the output is accurate to two decimal places).

Sample #1

Sample Input #1

10 
56 12 1 99 1000 234 33 55 99 812

Sample Output #1

3 2 7 8 1 4 9 6 10 5
291.90

draw attention to sth.

\(1\le n \leq 1000\)，\(1\le t_i \leq 10^6\)No guarantees\(t_i\) No repetition.

Thoughts:

  • We can adopt a greedy strategy by placing the person with the slowest receiving time at the back of the queue, so that the queue for the people at the back of the queue is shorter, this is the result that our intuition tells us, and, this is a locally optimal solution to the greedy strategy, we just need to place the person with the longest receiving time as far as possible at the back of the queue to receive the water, so that other people will wait for a shorter amount of time, and at the end of the day the total time to receive the water is the least amount of time.
  • So can a catch-all strategy like ours be rigorously mathematically proven? Actually, most of the time, the idea of our greedy strategy is just very normal common sense, and as long as we can't come up with an obvious counterexample to prove that our strategy doesn't work, we can use the greedy strategy, but this is a question where we can actually come up with a rigorous mathematical proof of the feasibility of our strategy.

Demonstrate the feasibility of the strategy

  • It can also be seen here that greedy strategies often go hand in hand with sorting, enumerating the optimal solutions one at a time and ultimately reaching the optimal result!

Code:

#include<algorithm>
#include<iostream>
using namespace std.
struct people {
struct people { int t; int id; int
struct people { int t; int id; int
}a[1005].
// Sort people in ascending order by time of water reception
bool compare(people& a, people& b) {
return < ;
}
int n;
int main()
int n; int main() {
cin >> n; for (int i = 1; i <= n; i++) {
for (int i = 1; i <= n; i++) {
cin >> a[i].t;
a[i].id = i;
}
sort(a + 1, a + 1 + n, compare);
for (int i = 1; i <= n; i++) {
cout << a[i].id << " ";
}
cout << endl;
double sum = 0;
    // Why ✖(n-i) here, because when the first person takes a shower, the n-1 people behind him have to wait for it, and the second person, the n-2 people behind him have to wait for him again
for (int i = 1; i <= n - 1; i++) sum += a[i].t*(n-i);
double average = sum / n; printf("%.2l")
printf("%.2lf", average); return 0;; double average = sum / n; printf("%.2lf", average)
return 0; }
}

Explanation of part of the code.

countsumsection involves the following code snippet:

double sum = 0;
for (int i = 1; i <= n - 1; i++)
    sum += a[i].t * (n - i);

The purpose of this code is to compute the value of the weighted average, which specifically means that the value of the weighted average is computed after a survey of the people according to thetAfter the attributes are sorted, calculate the waiting time of each person in the queue multiplied by the sum of the number of people behind them. Let's analyze why we multiply the(n - i)：

  1. Impact of sequencing：

    • arraysa[] in accordance witht Attributes are sorted from smallest to largest.
    • After sortinga[i].t denotei Individual processing time.

  2. Calculation of waiting time：

    • In the sorted order, if the firsti individual in the queue, then he is preceded by thei - 1 individual, so his waiting time is the sum of the processing times of all the previous individuals.

  3. Principles of Weighted Summation：

    • For the firsti Individuals who have a waiting time ofa[i].t * (n - i). Here.(n - i) The number of people behind him is indicated, since everyone behind him has to wait for his processing time.

  4. Calculate the sum：

    • sum += a[i].t * (n - i) It is the sum of each person's wait time multiplied by the number of people behind them to get the total weighted wait time.

  5. Final average：

    • average = sum / n It is the sum of this weighted waiting time divided by the total number of peoplen, which gets you the average wait time per person.

Therefore, multiplying(n - i) The manipulation was done to correctly calculate the contribution of each person's waiting time to the overall weighted average, ensuring that the average was correctly calculated as required by the question.

<Previous Next>