解法:贪心,加上前缀和的变形
查看原帖
解法:贪心,加上前缀和的变形
263107
LG197600楼主2021/1/26 14:54

#核心:谁用的时间少,谁先来

#include <time.h>
#include <string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>

using namespace std;

const int  maxn = 10001;

typedef struct node
{
	int number;
	int time;
};

bool cmp(node n1, node n2)
{
	return n1.time < n2.time;
}

int main()
{
	int n;
	cin >> n;
	node person[maxn];
	for (int i = 1; i <= n; i++)
	{
		cin >> person[i].time;
		person[i].number = i;//记录第i个人的下标
	}
	sort(person + 1, person + n + 1, cmp);//快排,谁用的时间少,谁先来
	for (int i = 1; i <= n; i++)
	{
		if (i != n)
			cout << person[i].number << " ";
		else cout << person[i].number << endl;
	}
	int sum[maxn];
	memset(sum, 0, sizeof(sum));
	double ans = 0;//用ans来记录除了第一个人,剩下的所有人的时间的前缀和,因为第一个人不需要等。
	for (int i = 2; i <= n; i++)
	{
        第i个人需要等的时间是前面i-1个人所用的时间加上第i-1个人所用的时间。
		sum[i] = sum[i - 1] + person[i-1].time;
		ans += sum[i];
	}
	printf("%.2lf", ans / n);
	return 0;
}
2021/1/26 14:54
加载中...