有n个人排队到r个水龙头去打水,他们装满水桶的时间t1、t2………tn为整数且各不相等,应如何安排他们的打水顺序才能使他们总共花费的时间最少?通过键盘输入排队打水的人数以及每人打水的时间和水龙头数,使用贪心算法求出所有人完成打水总共花费的时间的最小值。C语言
时间: 2024-04-27 16:06:58 浏览: 77
实现如下:
#include <stdio.h>
#include <stdlib.h>
// 比较函数,用于快速排序
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, r;
printf("请输入排队打水的人数和水龙头数:\n");
scanf("%d%d", &n, &r);
int* t = (int*)malloc(sizeof(int) * n);
printf("请输入每个人打水的时间:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &t[i]);
}
// 按照打水时间排序
qsort(t, n, sizeof(int), cmp);
int* a = (int*)malloc(sizeof(int) * r);
for (int i = 0; i < r; i++) {
a[i] = 0;
}
int ans = 0;
for (int i = 0; i < n; i++) {
// 找到最早完成的水龙头
int minIndex = 0;
for (int j = 1; j < r; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
// 计算完成时间并更新水龙头状态
int finishTime = a[minIndex] + t[i];
a[minIndex] = finishTime;
// 更新答案
if (finishTime > ans) {
ans = finishTime;
}
}
printf("所有人完成打水总共花费的时间的最小值为:%d\n", ans);
free(t);
free(a);
return 0;
}
阅读全文