在c语言中:输入这n个人取水所需的时间,为t1, t2, …, tn,其中ti为正整数。由于这n个人是同时到达取水点的,而且这n个人都很谦让,因此我们可以随意安排他们的接水顺序。现在要求这n个人接水的一种先后顺序,使得这n个人的平均等待时间最小。事实上,总等待时间最小一定就意味着平均等待时间最小,所以本题要求输出最小的总等待时间。
时间: 2024-03-25 12:41:02 浏览: 57
c语言读取时间
这是一道经典的调度问题,可以使用贪心算法来解决。具体做法是将所有人的取水时间从小到大排序,然后依次安排他们的顺序,使得取水时间短的人先取水。这样可以最大程度地减少等待时间,从而达到平均等待时间最小的目的。
下面是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, i;
int *t, *w;
long long ans = 0;
scanf("%d", &n);
t = (int*)malloc(n * sizeof(int));
w = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
scanf("%d", &t[i]);
}
qsort(t, n, sizeof(int), cmp);
w[0] = t[0];
ans += w[0];
for (i = 1; i < n; i++) {
w[i] = w[i - 1] + t[i];
ans += w[i];
}
printf("%lld\n", ans);
free(t);
free(w);
return 0;
}
```
首先输入n个人的取水时间,然后使用qsort()库函数进行排序。接着,使用一个数组w来记录每个人的等待时间,计算总等待时间ans。最后输出ans即可。
阅读全文