排队接水

题目描述

有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。

输入格式

第一行为一个整数 \(n\)。

第二行 \(n\) 个整数，第 \(i\) 个整数 \(T_i\) 表示第 \(i\) 个人的等待时间 \(T_i\)。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例 #1

样例输入 #1

10 
56 12 1 99 1000 234 33 55 99 812

样例输出 #1

3 2 7 8 1 4 9 6 10 5
291.90

提示

\(n \leq 1000,t_i \leq 10^6\)，不保证 \(t_i\) 不重复。

当 \(t_i\) 重复时，按照输入顺序即可（sort 是可以的）

解析

好久都没见过这么简单的贪心了啊

贪心宗旨：将时间少的排在前面（用\(sort\)排序）

只用定义一个结构体数组就行啦

最后再用一个求和公式

代码

#include <bits/stdc++.h>
using namespace std;
struct aaa{
	int ti,num;//定义结构体aaa      
}a[1010];//定义结构体数组
bool cmp(aaa x,aaa y)//定义“小于”运算符
{
	return x.ti<y.ti;    
}
int main()
{
	int n;
	double time=0;
	cin >> n;    
	for(int i=1;i<=n;i++)   
	{
		cin >> a[i].ti;
		a[i].num=i;//序号存起来              
	} 
	sort(a+1,a+n+1,cmp);//排序
	for(int i=1;i<=n;i++)
	{
		cout << a[i].num << ' '; //先把简单的做了，输入由小到大的编号
	}
	cout << endl;//要换行
	int i;
	for(int j=n-1;j>=1;j--) //等待人数的计数器，由n-1开始
	{
		i=n-j;//这是个规律，当前最少时间的人序号和要等待的人数之和=n
		time+=a[i].ti*j; //累加                  
	}
	
//   算平均，保留两位小数
//	printf("%.2lf",time/n);
	cout << fixed << setprecision(2) << time/n;
	return 0; 
}