贪心算法——排队打水问题
*/6.3 排队打水问题：有n个人排队到r个水龙头去打水，他们装满水桶的时间为t1,t2,…,tn为正整数且个不相等。
应如何安排他们打水顺序才能使他们花费的时间最少。
算法分析:时间总和=等待时间+装水时间。采用贪心思想。先sort()，默认将装水时间从小到大排序。
n个人，r个水龙头，可以以水龙头为序将队伍序分割成n/r个小组，每小组的成员分别对应r个位置。
实际上就是将人依序分成r个小队打水。比如有三个水龙头，分成三个小队，1、4、7… ，2、5、8…，3、6、9…
可以验证是否符合贪心：从序号第1的人开始依次往后选择水龙头，为了等待时间+灌水时间最小是不是该这样站队？
*/
#include
#include
#include //C++标准模板库STL，用到sort排序
using namespace std;
int main()
{
int a[1000],b[1000],n,r; //a数组存放每个人的装水时间，b数组存放每个人的总时间（等待时间+打水时间）
memset(a,0,sizeof(a)); //数组初始化为0
memset(b,本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！