洛谷P1223

发表于

题目：P1223 排队接水
题目需要输出平均时间最短的排队顺序和平均等待时间，用贪心可解。

创建结构体数组存储初始的序号和所用时间，再自定义cmp函数，对时间从小到大排序，最后输出序号。

平均等待时间为每个人等待时间的和除以人数，设共有n个人，第i个人接水时他身后所有人都需要等待t的时间，由此可以推出方程为

总程序为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
struct dui
{
	int num, time;
}a[1010];
bool cmp(dui a, dui b)
{
	if (a.time != b.time)
		return a.time < b.time;
	else
		return a.num < b.num;
}

signed main()
{
	double sum = 0;
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		a[i].num = i;
		cin >> a[i].time;
	}
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++)
	{
		sum += a[i].time * (n - i);
		cout << a[i].num << " \n"[i == n];
	}
	cout << fixed << setprecision(2) << sum / n << endl;
	return 0;
}