贪心算法题目合集

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;
}

原文地址：https://blog.csdn.net/m0_73693552/article/details/144020981

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！