All in one 1319 - queue for water

【 Title Description 】

Yes n People line up in front of a tap to get water , Suppose everyone gets water for Ti, Please program to find this n An order in which individuals line up , bring n The average waiting time of an individual is the smallest .

【 Input 】

There are two lines , First act n(1≤n≤1000); The second line represents the second 1 Personal to the third n Each person's water receiving time T1,T2,…,Tn Between each data is 1 A space .

【 Output 】

There are two lines , The first behavior is a queuing order , namely 1 To n An arrangement of ; The second behavior is the average waiting time under this arrangement scheme ( The output is accurate to two decimal places ).

【 sample input 】

10							
56 12 1 99 1000 234 33 55 99 812

【 sample output 】

3 2 7 8 1 4 9 6 10 5
291.90

Topic summary ：

The first i Personal waiting time = The first i-1 Personal water connection time + Waiting time , Our task is to minimize the average waiting time , That is, everyone should wait for the shortest time , Let the person who needs a short time get the water first . This problem requires a greedy algorithm .

analysis ：

1. Let the time be short , Sorting is required

2. The average time is accumulated directly when entering , Directly divide the output by the total number of people

3. The output is required to keep two decimal places , Use printf

Code ：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id;
	int t;
}a[1005];
bool cmp(node x,node y)
{
	return x.t<y.t;
}
int main()
{
	double ans=0;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].t;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	int j=1;
	for(int i=n-1;i>0;i--)
	{
		ans+=i*a[j].t;
		j++;
	}
	for(int i=1;i<=n;i++) cout<<a[i].id<<" ";
	cout<<endl;
	printf("%.2f",ans/n);
	return 0;
}