【2030】排队打水问题

Time Limit: 3 second
Memory Limit: 2 MB

有n个人排队到r个水龙头去打水，他们装满水桶的时间t1，t2，....tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少。

Input

输入文件两行
第一行输入打水人数n，水龙头数r。用空格隔开
第二行依次输入n个人的打水时间t1，t2，....tn，用空格隔开(1≤n≤1000)。

Output

输出总共花费的时间。（最后用换行结束）

Sample Input

4 2
2 6 4 5

Sample Output

23

【题解】

样例的取法

2 4 5 6

注意只有两个水龙头

先每个人都等2个单位 ->8

0 2 5 6

再每个人都等两个单位 这下只有3个人等了 -> 6

0 0 3 6

再每人等3个单位 这下只有2个人等了 -> 6

0 0 0 3

最后一个人再等3个单位,->3

总共23个单位.

贪心法，每次装水的时候先让花费时间少的人先装，这样其他所有人都在等，他们等的时间就会比较少，而这个花费时间少的人打完之后，一起等的人就变成N-1个了，剩下的时间可能比较长，但是人数变少了，肯定比n个人一起等时间长的花费时间来得短。先排序，然后用几个变量作为头尾不断减就好。

 

【代码】

#include <cstdio>

const int MAXN = 1000;

int n,r,a[MAXN*10+100],sum = 0,num;

void input_data() //输入数据
{
    for (int i = 1;i <= MAXN*10;i++) //先置0 这可以作为跳出循环的边界
        a[i] = 0;
    scanf("%d %d",&n,&r);
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    num = n; //num没用到。
}

void kp(int l,int r) //快排一遍。 从小到大排
{
    int i = l,j = r,m = a[(i+j)/2];
    do
    {
        while (a[i] < m) i++;
        while (m < a[j]) j--;
        if (i <= j)
            {
                int t = a[i];a[i] = a[j];a[j] = t;
                i++;j--;
            }
    }
    while (i <= j);
    if (l < j) kp(l,j);
    if (i < r) kp(i,r);
}

void get_ans()
{

    int i = 1,j = 1 + r -1; //这是头尾指针 要注意超过n变成n 这里的头尾指的是能在有限的水龙头上打水的人。
    if (j > n) j = n;
    while (a[i] > 0) //如果还有东西可以减 那么。。
        {
            int d = a[i]; //先获取要花费的时间(取最短时间)
            for (int k = i;k <= j;k++) //水龙头上的人每个人都减少一些时间
                a[k]-=d;
            for (int k = i;k <= n;k++) //每个在等的人都增加时间。
                sum+=d;
            while (a[i] == 0 && i<=n ) i++; //找下一个在等的人。
            j = i + r -1;
            if (j > n) j = n;
        }
}

void output_ans()
{
    printf("%d\n",sum);
}

int main()
{
    input_data();
    kp(1,n);
    get_ans();
    output_ans();
    return 0;
}