算法提高 排隊(duì)打水問題 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB 提交此題 問題描述 有n個(gè)人排隊(duì)到r個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間t1、t2………..tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費(fèi)的時(shí)間最少？ 輸入格式 第一行n，r (n<=500,r<=75) 第二行為n個(gè)人打水所用的時(shí)間Ti (Ti<=100)； 輸出格式 最少的花費(fèi)時(shí)間 樣例輸入 3 2 1 2 3 樣例輸出 7
數(shù)據(jù)規(guī)模和約定 其中80%的數(shù)據(jù)保證n<=10
首先 等的時(shí)間最短是這個(gè)題最重要的，那么就需要 讓接水時(shí)間最小的人放在前面， 之后，要讓接水的人等的時(shí)間最短
創(chuàng)建兩個(gè)數(shù)組 ，一個(gè)代表接水的等待時(shí)間 ，一個(gè)代表人 接水的人所在的水龍頭的等待時(shí)間加上去 然后后面的人優(yōu)先選擇等待時(shí)間最少的水龍頭去接水。
一共進(jìn)行n次排序，每次的為r*lg（r） 所以復(fù)雜度為n*r*lg（r） 數(shù)據(jù)最大為500*75*9 很小- -
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <map>using namespace std;int d[505];//等待的時(shí)間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);//把等待時(shí)間最小的水龍頭排到前面 //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; }}新聞熱點(diǎn)
疑難解答
