题目描述

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

输入格式

• 第一行为一个整数 n。
• 第二行 n 个整数，第 i 个整数表示第 i 个人的等待时间。

输出格式

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

样例 #1

样例输入 #1

10 
56 12 1 99 1000 234 33 55 99 812

样例输出 #1

3 2 7 8 1 4 9 6 10 5
291.90

提示

n ≤ 1000, 等待时间 ≤ 10^6，不保证每个人的等待时间不重复。当存在重复的等待时间时，按照输入顺序即可。

题解

经过分析，将所有元素从小到大排序可以得到答案。
需要注意的点有：

• 存储等待时间之和的变量 sum 要使用 long long 类型存储
• 存储平均等待时间的变量要用 double 类型存储

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b);

int main() {
  int n, i, j;
  long long sum = 0; // int 类型不够用，要用 long long
  scanf("%d", &n);
  int *t = (int *)malloc(n * sizeof(int));
  int *index = (int *)malloc(n * sizeof(int));
  for (i = 0; i < n; i++)
    scanf("%d", t + i);

  for (i = 0; i < n; i++)
    index[i] = i + 1;

  for (i = 0; i < n; i++)
    for (j = n - 1; j > i; j--)
      if (t[i] > t[j]) {
        swap(&t[i], &t[j]);
        swap(&index[i], &index[j]);
      }

  for (i = 0; i < n; i++) {
    printf("%d ", index[i]);
    sum += (n - i - 1) * t[i];
  }

  // float 不够用，必须 double
  printf("\n%.2lf", (double)sum / (double)n);
  free(t);
  free(index);
  return 0;
}

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}