题目描述 马上就要过年啦!X星球决定给每个人发一份福利,不过这份福利需要排队去X星设置在各个地方的福利发放点领取,福利据说是一个神秘大礼包。 由于每个人在2021年为X星做出的贡献不一样,因此福利包中的礼物也不一样,领取福利所需要的时间也不一样。 现在有N个X星人到达了某一个福利发放点,很遗憾这个福利发放点只有一位工作人员在发放福利包,现在已知每个X星人领取福利包所需要时间(不包括排队等待时间,单位:分钟)。 为了让所有人的平均等待时间最少,需要你设计一个算法来安排领取顺序,请编写程序输出最少平均等待时间(单位:分钟),结果四舍五入保留两位小数。 输入 单组输入,每组输入包含两行。 第1行输入一个正整数N,表示等待领取福利包的X星人的数量(N<=1000)。 第2行输入N个正整数,分别对应N个X星人每人领取福利包所需时间(单位:分钟),每个X星人的领取时间均不会超过100分钟。 输出 输出最少平均等待时间(单位:分钟),结果四舍五入保留两位小数。 样例输入 Copy 4 4 3 1 4 样例输出 Copy 3.25
时间: 2024-02-16 20:00:43 浏览: 17
这是一道经典的调度问题,可以使用贪心算法来解决。我们需要将等待领取福利包的X星人按照领取时间从小到大排序,然后依次让他们进入福利发放点领取福利包。对于每个人,我们都需要计算他等待的时间和他领取福利包的时间,然后将所有人的等待时间相加并除以总人数,就可以得到最少平均等待时间。
Java代码实现如下:
```java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 等待领取福利包的X星人的数量
int[] times = new int[n]; // 每个X星人领取福利包所需时间列表
for (int i = 0; i < n; i++) {
times[i] = scanner.nextInt();
}
// 将每个X星人按照领取时间从小到大排序
Arrays.sort(times);
double totalWaitTime = 0; // 所有X星人的等待时间之和
double totalEndTime = 0; // 所有X星人的领取福利包的结束时间之和
for (int i = 0; i < n; i++) {
totalWaitTime += totalEndTime;
totalEndTime += times[i];
}
// 计算最少平均等待时间并输出
double result = totalWaitTime / n;
System.out.printf("%.2f", result);
}
}
```
这个算法的时间复杂度为 $O(n \log n)$,其中 $n$ 是等待领取福利包的X星人的数量。排序需要 $O(n \log n)$ 的时间,后面的遍历需要 $O(n)$ 的时间。所以总的时间复杂度为 $O(n \log n)$。