洛谷P1223 排队接水

排队接水

题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例 #1

样例输入 #1

10 
56 12 1 99 1000 234 33 55 99 812
1
2

样例输出 #1

3 2 7 8 1 4 9 6 10 5
291.90
1
2

提示

$n\le 1000,t_i\le 10^6$，不保证 $t_i$ 不重复。

当 $t_i$ 重复时，按照输入顺序即可（sort 是可以的）

思路：再该代码中，T代表输入进来的每个人需要接水时间，p代表复制T数组，q代表最后排序后，记录下每个人的序号，然后首先对T排序，排序后，用T和p比较，看谁原来在哪个位置，然后用q记录下来当初的位置，记录下来后就把p数组里面的该值赋为0，防止下次遍历重复在该值退出循环，至此，我们已经获取到我们想要的所有数值，可以输出了！
该算法除了排序算法（我使用的冒泡，因为使用起来顺手）可能不是最优，但是该思想值得思考，如若有更好的想法，欢迎各大朋友私聊我！！！
代码如下（编译器是dev，语言是C语言）：

#include
int n,T[1005],p[1005],i,j,temp,q[1005];
double sum = 0;
int main(){
    scanf("%d",&n);
    for(i = 1;i<=n;i++){
        scanf("%d",&T[i]);
        p[i] = T[i];
    }
    for(i = 1;i<=n;i++){
        for(j = i+1;j<=n;j++){
            if(T[i]>T[j]){
                temp = T[i];
                T[i] = T[j];
                T[j] = temp;
            }
        }
    }
    for(i = 1;i<=n;i++){
        sum = sum + T[i]*(n-i);
        for(j = 1;j<=n;j++){
            if(T[i] == p[j]){
                p[j] = 0;
                q[i] = j;
                break;
            }
        }
    }
    for(i = 1;i<=n;i++){
        printf("%d ",q[i]);
    }
    sum = sum/n;
    printf("\n%.2lf",sum);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35