桶排序思想 求解打水问题

解题思路:首先我们先把每个人打水时间从小到大排序  其次确定每只水龙头最多可以有多少人排队 依次把这些从小到大的时间放到每个水龙头。

注意事项:  计算每个水龙头的等待时间，最后一个人的不用加，其次第三个人等待的时间是第一个加第二个

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

const int N=10000;

int a[N]; 

int cnt;

int main()

{

    int n,m;

    cin>>n>>m;

    //每个水龙头最大容纳数

    int max=n/m+1;

    int b[N][max]={0}; 

    for(int i=0;i<n;i++)

    {

    cin>>a[i];

}

sort(a,a+n);

for(int i=0;i<m;i++)

{

     int j=i;

     cnt=0;

     while(j<n)

     {

        //每个水龙头里的等待时间也是一个等差数列 公差是水龙头个数

         b[i][cnt++]=a[j];

         j+=m;

     }

}

int sum=0;

for(int i=0;i<m;i++)

{

     sort(b[i],b[i]+max);

     //计算每个水龙头的等待时间，除去最后一个（最大等待时间）

     for(int j=0;j<max-1;j++)

     {

         for(int x=j;x<max-1;x++)

         {

              //第一轮加上所有第一个的等待时间，第二轮加上第二个的等待时间......

             //第一轮加的全是b[0][0]

              sum+=b[i][j];

         }

     }

}

cout<<sum;

return 0;

}