算法提高 排队打水问题 时间限制：1.0s 内存限制：256.0MB 提交此题 问题描述 有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？ 输入格式 第一行n，r (n<=500,r<=75) 第二行为n个人打水所用的时间Ti (Ti<=100)； 输出格式 最少的花费时间 样例输入 3 2 1 2 3 样例输出 7
数据规模和约定 其中80%的数据保证n<=10
首先 等的时间最短是这个题最重要的，那么就需要 让接水时间最小的人放在前面， 之后，要让接水的人等的时间最短
创建两个数组 ，一个代表接水的等待时间 ，一个代表人 接水的人所在的水龙头的等待时间加上去 然后后面的人优先选择等待时间最少的水龙头去接水。
一共进行n次排序，每次的为r*lg（r） 所以复杂度为n*r*lg（r） 数据最大为500*75*9 很小- -
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <map>using namespace std;int d[505];//等待的时间int x[505];//接水的人int main(){ int n,r; while(cin>>n>>r) { int sum=0; memset(d,0,sizeof(d)); for(int i=0;i<n;i++) { cin>>x[i]; } sort(x,x+n); for(int i=0;i<n;i++) { sort(d,d+r);//把等待时间最小的水龙头排到前面 //for(int j=0;j<r;j++)cout<<d[j]<<' ';cout<<endl; sum+=d[0]+x[i]; d[0]+=x[i]; // for(int j=0;j<r;j++)cout<<d[j]<<' ';cout<<endl<<sum<<endl;cout<<endl<<endl; } cout<<sum<<endl; }}新闻热点
疑难解答
