可达鸭J3题目 排队接水

题目描述

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序（若有多种顺序则编号小的在前）， 使得n个人的平均时间花费最小。

输入描述

输入文件共两行，第一行为n；第二行分别表示第 1 个人到第n个人每人的接水时间T1，T2，…，Tn，每 个数据之间有 1 个空格。n<200.

输出描述

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

样例

输入

10							
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
532.00

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
double sum;
struct man{
	int num,id;
}t[208];
bool cmp(man a,man b){
	if(a.num==b.num) return a.id<b.id;
	else return a.num<b.num;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>t[i].num;
    	t[i].id=i;
	}
	sort(t+1,t+1+n,cmp);
	for(int i=1;i<=n;i++){
		cout<<t[i].id<<" ";
		sum=sum+(n-i+1)*t[i].num;
	}
	sum/=n;
	printf("\n%.2lf",sum);
	return 0;
}