第六章 贪心算法 6.1 打水问题

/*********************************
 * 名称：第六章 打水问题 
 * 2020-12-22
 ********************************/
#include <iostream>
#include <algorithm>    //sort()
#include <cstring>      //memset()

using namespace std;

const int MAXN=1000;    //数组大小 
int a[MAXN],s[MAXN];    //人均打水时间 

int main(){
    int n,r,i,j=0,minx=0;
    memset(s,0,sizeof(s)); //数组初始化 
    cin>>n>>r;             //n人，r个龙头 
    for(i=1;i<=n;i++)
        cin>>a[i];         //依次输入人均打水时间 
    sort(a+1,a+n+1);       //对所有的时间排序
    for(i=1;i<=n;i++){
        j++;               //两个水龙头 
        if(j==r+1)
            j=1;           //前r个人人为一组，第r+1个人回到第一个水龙头
        s[j]+=a[i];        //加上等待时间
        minx+=s[j];        //累加
    }
    cout<<minx<<endl;
    return 0;
}

测试1：

4 2
2 5 4 6
23
--------------------------------
Process exited after 6.933 seconds with return value 0
请按任意键继续. . .