高质量题解|【贪心】排队接水

题目大意

每个人都有接水时间和下标，算出接水的最小时间，输出接水顺序的下标和最少时间的平均时间

考纲知识点

输入输出、分支结构、算术运算符、循环结构、结构体基础、结构体排序、自定义函数、贪心算法、基础数据类型、变量的定义以及使用

数据范围

$1$ $≤$ $n$ $≤$ $1000$

$1$ $≤$ $T_i$ $≤$ $1000$

解题思路

要想使最后的每个人打水的时间最少，就需要让打水时间短的人先打水
用结构体记录下每个人的打水时间和下标，定义一个范围为 $1010$ 的结构体数组
输入结构体中每个人的打水时间，下标就是目前的 $i$
对数组进行升序排序:

1. 两个人的打水时间不同，按照打水时间从小到大排序
2. 两个人的打水时间相同，按照下标从小到大排序

排序后从小到大依次都是接水时间短到接水时间长的人
先输出每个人的下标，用 $sum$ 记录下最终的时间，公式如下:

$$a_i.t\times(n-i)$$

最后换行，保留两位小数输出平均时间

参考程序

#include <bits/stdc++.h>
using namespace std;
//定义结构体储存当前接水的人的耗时和下标 
struct node{
	int t,id;
}a[1010]; 
bool cmp(node x,node y){
	if(x.t != y.t){
        return x.t < y.t;//定义排序规则，接水时间短的人先去接水 
    }else{
        return x.id < y.id;
    }
}
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i].t;
		a[i].id = i;//给接水的人id赋值 
	}
	sort(a + 1,a + n + 1,cmp);
	double sum = 0;
	for(int i = 1;i <= n;i++){
		cout << a[i].id << " ";
		sum += a[i].t * (n - i);
	}
	cout << endl;
	printf("%.2f",sum / n);
	return 0;
}

时间复杂度

$O(n \log n)$(线性对数时间复杂度)

空间复杂度

$O(n)$(线性空间复杂度)