算法提高 打水問題 時間限制：1.0s 內存限制：512.0MB 提交此題 問題描述 N個人要打水，有M個水龍頭，第i個人打水所需時間為Ti，請安排一個合理的方案使得所有人的等待時間之和盡量小。 輸入格式 第一行兩個正整數N M 接下來一行N個正整數Ti。 N,M<=1000，Ti<=1000 輸出格式 最小的等待時間之和。（不需要輸出具體的安排方案） 樣例輸入 7 3 3 6 1 4 2 5 7 樣例輸出 11 提示 一種最佳打水方案是，將N個人按照Ti從小到大的順序依次分配到M個龍頭打水。 例如樣例中，Ti從小到大排序為1，2，3，4，5，6，7，將他們依次分配到3個龍頭，則去龍頭一打水的為1，4，7；去龍頭二打水的為2,5；去第三個龍頭打水的為3,6。 第一個龍頭打水的人總等待時間 = 0 + 1 + (1 + 4) = 6 第二個龍頭打水的人總等待時間 = 0 + 2 = 2 第三個龍頭打水的人總等待時間 = 0 + 3 = 3 所以總的等待時間 = 6 + 2 + 3 = 11
貪心的策略。 為了讓等待時間最短，所以讓小的先去接水 為了讓總體等待時間最短，所以讓小的去等待時間小的地方接水 這樣 下次在這個水龍頭的接水等待時間最短
#include <iostream>#include <string>#include <cstring>#include <stdio.h>#include <cmath>#include <algorithm>using namespace std;int a[10000];int d[10000];int main(){ int n,m; while(cin>>n>>m) { memset(d,0,sizeof(d)); memset(a,0,sizeof(a)); for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n);//排序 優先讓小的接水 int sum=0; for(int i=0;i<n;i++) { sort(d,d+m);//排序，讓小的去等待時間最短的地方接水 sum+=d[0]; d[0]+=a[i];//將最小的那個水龍頭加上等待時間 } cout<<sum<<endl; }}新聞熱點
疑難解答
