贪心算法题目合集

1319：【例6.1】排队接水 贪心策略思想

1319：【例6.1】排队接水

贪心算法与其说是算法，不如说是一种风格：每次做事情都选择自己认为的最优解。

贪心算法的题很多都和排序有关，且大都能用STL的sort函数和qsort函数解决。

例如这道排队接水，求怎么做才能让每人的平均接水时间最少，用贪心策略的话，就是谁接水用的时间最少，谁就先接水。同时所有人接水时，每个人总共消耗的时间是等待时间加接水时间，等待时间是之前的人接水用的时间，这个可以用递推式去计算。另外最后一个人的接水时间并不算进总的等待时间里。

例如这个样例：

5
1 2 3 4 5
//递推式
接水时间：1 2 3 4 5
实际耗时：1 3 6 10 15
等待时间：0 1 4 10 20

到这里，这题的思路就很清晰了：先排序，再用递推式去计算等待时间，最后求平均值即可。

#define _CRT_SECURE_NO_WARNINGS 1
/*
【输入样例】
10
56 12 1 99 1000 234 33 55 99 812
【输出样例】
3 2 7 8 1 4 9 6 10 5
291.90
*/

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;

struct info {
	int tim;
	int ord;
	info(int a = 0, int b = 0) {//构造函数初始化
		tim = a; ord = b;
	}
};
info t[1001];
bool cmp(info a, info b) {
	return a.tim < b.tim;
}

int main() {
	int n;
	double sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i].tim;
		t[i].ord = i;
	}
	sort(t + 1, t + n + 1, cmp);//STL的sort函数，底层是快排
	for (int i = 1; i <= n; i++) {
		cout << t[i].ord << " ";
        
        //之前的那个人的接水时间就是现在这个人的等待时间
		sum += double(t[i - 1].tim); 
		t[i].tim += t[i - 1].tim;
	}
	cout << endl;
	cout << fixed << setprecision(2) << (sum / n);//保留2位小数输出
	return 0;
}