算法提高 排隊打水問題 時間限制：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; }}新聞熱點
疑難解答
