【贪心算法T】排队打水问题（多处最优服务次序问题）

【问题描述】

有n个人排队到r个水龙头去打水，他们装满水桶的时间为t1,t2,…,tn为整数，且各不相同。求所有人打完水所用到的时间最少时间？

n和r都小于10

输入
两行, 第一行，人数n和水龙头数r；
第二行，n个数代表每个人打水所用的时间。
输出
打水所用的最少时间

样例输入
4 2
2 6 4 5
样例输出
23

【算法分析】

多处最优服务次序问题

【算法实现】

#include
#include
#include
using namespace std;double greedy(vector<int> client,int s)
{vector<int> service(s+1,0);vector<int> sum(s+1,0);int n=client.size();sort(client.begin(),client.end());int i=0,j=0;while(i<n){service[j]+=client[i];sum[j]+=service[j];++i;++j;if(j==s)j=0;}double t=0;for(i=0;i<s;++i)t+=sum[i];return t;
}
int main()
{vector<int> queue;int n,r;cin>>n>>r;int temp;for(int i=0;i<n;i++){cin>>temp;queue.push_back(temp);}cout<<greedy(queue,r);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！