排队打水问题 贪心

题目链接 

问题描述

　　有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

分析：贪心。每次将剩下接水花费时间最短的人排在等待时间最短的水龙头上，每一次加入一个人的时候水龙头的等待时间延长，需要重新排序。总的时间复杂度O(nlogr）其实也可以用优先队列优化，但是数据量不大，不优化也行

方法一:排序 

#include 
#include 
#include 
using namespace std;
const int N = 500+5, R = 80;
int men[N], tap[R];int main(int argc, char** argv) {int n, r;scanf("%d%d",&n,&r);for(int i = 0; i < n; i++)scanf("%d",&men[i]);sort(men, men+n);memcpy(tap, men, sizeof(int)*r);int ans = 0;for(int i = r; i < n; i++){ans += tap[0];tap[0] += men[i];				sort(tap, tap+r);}	for(int i = 0; i < r; i++)ans += tap[i];printf("%d\n",ans);return 0;
}

方法二：堆优化 

#include 
#include 
#include 
#include 
#include  
using namespace std;
const int N = 500+5;
int men[N];int main(int argc, char** argv) {int n, r;scanf("%d%d",&n,&r);for(int i = 0; i < n; i++)scanf("%d",&men[i]);sort(men, men+n); priority_queue, greater > pq;int ans = 0;for(int i = 0; i < r; i++){pq.push(men[i]);ans += men[i];}	for(int i = r; i < n; i++){int time = pq.top()+men[i]; pq.pop();ans += time;pq.push(time);				}printf("%d\n",ans);return 0;
}

输入格式

　　第一行n，r (n<=500,r<=75)
　　第二行为n个人打水所用的时间Ti (Ti<=100)；

输出格式

　　最少的花费时间

样例输入

3 2
1 2 3

样例输出

7

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