贪心算法6 排队接水问题

小咪咪 2022-05-09 12:56 224阅读 0赞

题目描述  
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1, t2 , ……, tn为整数且各不相同，应如何安排他们的打水顺序才能使他们花费的总时间最少? 只有一组输入数据哦。

输入  
4 2

2 6 4 5

输出  
23（所有人的花费时间总和）

样例输入  
4 2  
2 6 4 5  
样例输出  
23

![70][]

#include<iostream>
    #include<algorithm>
    #define MAXN 505
    int a[MAXN];//每个人打水的时间 
    int b[MAXN];//每个人花费时间 
    int sum=0;
    using namespace std;
    int main()
    {
    	//freopen("a.txt","r",stdin);
    	int n,r;
    	cin >> n >> r;
    	for(int i = 1; i <= n;++i)
    		cin >> a[i];
    	sort(a+1,a+1+n);
    	for(int i = 1; i <= n; ++i)
    		b[i] = a[i]; 
    	for(int i = r+1; i <= n; ++i)
    	{
    		b[i] = b[i-r] + a[i];//每个人花费的总时间 = 等待时间+打水时间 
    		//cout << "b[" << i <<"]= " << b[i] << endl; 
    	}
    			
    	for(int i = 1; i <= n; ++i)
    		sum += b[i];//总时间= 每个人花费的总时间之和 
    	cout << sum << endl;
    	return 0;
    		 
    }

![70 1][]

#include<iostream>
    #include<algorithm>
    #define MAXN 505
    int a[MAXN];//每个人打水的时间 
    int b[MAXN];
    using namespace std;
    int main()
    {
    	freopen("a.txt","r",stdin);
    	int n , t,i,j,k=0; 
    	   cin>>n>>t;
       for(i=1;i<=n;i++)cin>>a[i];
       sort(a+1,a+1+n); //按照打水时间从小到大快排
       j=0;k=0;
       for(i=1;i<=n;i++)
       {   j++;
           if(j>t)j=1;
           b[j]+=a[i];  //记录第i个水龙头的花费时间
          // cout << "b[" << j << "] = " << b[j] << endl;
           k+=b[j];   //累加总时间
          // cout << k << endl;
       }
       cout<<k<<endl;
       return 0;
    		 
    }

![70 2][]

[70]: /images/20220506/6c3757424f3c46818780e5ce1bfa4302.png
[70 1]: /images/20220506/4de094b4a2c94ebda346f08c9c8c2e08.png
[70 2]: /images/20220506/229ee188aba4472cb030fb81ac4c8d62.png