深入浅出学算法043-排队打水

Question

问题 A: 深入浅出学算法043-排队打水
时间限制 : 1.000 sec 内存限制 : 128 MB

使用贪心算法完成
题目描述
有N个人排队到1个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数，应如何安排他们的打水顺序才能使他们花费的时间最少？
输入
输入分2行，第一个数为N表示打水人数
第二行有N个数，为每人的打水时间
输出
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
如果有多种排队方式使得平均等待时间一样小，选择字典序最小的排队方式。
样例输入 Copy
10
56 12 1 99 1000 234 33 55 99 812
样例输出 Copy
3 2 7 8 1 4 9 6 10 5
532.00
提示
n<=1000
ti<=1e6，不保证ti不重复

附上我的代码，望各位指点一二

#include <bits/stdc++.h>
using namespace std;
int n,tn[10000],s[10000],ren;
double ttime;
int paixv(int aj[10000]){
    int min=1;
    for(int i=1;i<=n;i++){
        if(aj[i]<aj[min]&&aj[i]!=-1){
            min=i;
            aj[i]=-1;
        }
    }
    return min;
}
int main(){
    int aj[10000];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&tn[i]);
        aj[i]=tn[i];
    }
    for(int i=1;i<=n;i++){
        s[i]=paixv(aj);
        aj[s[i]]=-1;
        printf("%d ",s[i]);
        ttime=ttime+tn[s[i]]*(n-i);
    }
    ttime/=(n-1);
    printf("\n%.2f\n",ttime);
    return 0;
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

深入浅出学算法043-排队打水

问题描述：有 N 人排队到 1 个水龙头去打水，他们装满水桶的时间为 T1,T2,…,Tn 为整数，应该如何计算排队打水的总时间？

解决方案：使用 priority queue 实现，时间复杂度 O(NlogN)。

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> T(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }
    priority_queue<int> pq;
    for (int i = 0; i < N; i++) {
        pq.push(T[i]);
    }
    int res = 0;
    while (pq.size() > 1) {
        int t1 = pq.top();
        pq.pop();
        int t2 = pq.top();
        pq.pop();
        res += t1 + t2;
        pq.push(t1 + t2);
    }
    cout << res << endl;
    return 0;
}

这个算法的思路是：首先将所有时间排序，然后从小到大依次取出两个时间，计算它们的和，并将和作为新的时间加入队列中。最后，队列中剩下的时间即为总时间。