蓝桥杯 ADV-148 算法提高排队打水问题（贪心）

问题描述
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入格式
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
输出格式
最少的花费时间
样例输入
3 2
1 2 3
样例输出
7
数据规模和约定
其中80%的数据保证n<=10

分析：按照时间从大到小的顺序排序后即为打水的顺序~每个人依次进入队列1…r、1…r、1…r……对于前面可以排满的且不是队列最后一排的人，每排满一行，总时间等于自身打水的时间加上前面所有人打水的时间~对于每个队列的最后一个人(或者倒数第二个人)，总时间等于自身打水的时间加上前面这一列所有人打水的时间~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n, r;
    scanf("%d %d", &n, &r);
    int *a = new int[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    int ans = 0;
    int cnt = n/r;
    int index = 0;
    while(cnt--) {
        for(int j = 0; j < index; j++)
            ans += a[j];
        for(int i = 0; i < r; i++)
            ans += a[index++];
    }
    while(index < n) {
        int t = index % r;
        while(t < n) {
            ans += a[t];
            t += r;
        }
        index++;
    }
    cout << ans;
    delete [] a;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

int n, r;

scanf("%d %d", &n, &r);

int *a = new int[n];

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

scanf("%d", &a[i]);

}

sort(a, a+n);

int ans = 0;

int cnt = n/r;

int index = 0;

while(cnt--) {

for(int j = 0; j < index; j++)

ans += a[j];

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

ans += a[index++];

}

while(index < n) {

int t = index % r;

while(t < n) {

ans += a[t];

t += r;

}

index++;

}

cout << ans;

delete [] a;

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版