上海建设局网站 招聘,上海闵行做网站的公司,视频网站如何赚钱,aso优化师工作很赚钱吗问题描述#xff1a;设有n个顾客同时等待一项服务。顾客i需要的服务时间为#xff0c;共有s处可以提供此项服务。应该如何安排n个顾客的服务次序#xff0c;才能使平均等待时间达到最小#xff1f;平均等待时间是n个顾客的等待服务时间的总和除以n。 算法设计#xff1a;对… 问题描述设有n个顾客同时等待一项服务。顾客i需要的服务时间为共有s处可以提供此项服务。应该如何安排n个顾客的服务次序才能使平均等待时间达到最小平均等待时间是n个顾客的等待服务时间的总和除以n。 算法设计对于给定的n个顾客需要的服务时间和s的值计算最优服务次序。 数据输入由文件input.txt给出输入数据。第1行有2个正整数n和s表示有n个顾客且有s处可以提供服顾客需要的服务。接下来的1行中有n个正整数表示n个顾客需要的服务时间。 结果输出将计算的最小平均等到时间输出到文件output.txt。 基本思想
该题是贪心算法的典型只需要将所有的任务按照截至时间递增进行排序然后将任务逐个分配给每一个服务器。即将等待的人逐个分配到每一个服务处。重在于统计每一个任务等待时间然后计算平均等待时间。需要注意的是这里的等待时间是相对于完成任务的时间点等待时间包括完成任务所花费的时间和等待分配到的时间即等待时间执行时间执行前等待分配的时间 具体代码实现如下
#includestdio.h//选出当前等待时间最小的服务处
int SelectMin(int* wait,int s)
{int min wait[0];int index 0;for (int i 0; i s; i) {if (min wait[i]) {min wait[i];index i;}}return index;
}//安排顾客计算平均等待时间
int Greedy(int* wait, int *arr, int n,int s)
{int sum 0;int index;for (int i 0; i n; i) {index SelectMin(wait, s);wait[index] arr[i];sum wait[index];}return sum / n;
}//对顾客的执行时间进行从小到大的排序
void sort(int* arr,int n)
{int temp;for(int i0;in;i){for(int j0;ji;j){if(arr[j]arr[j1]){temparr[j];arr[j]arr[j1];arr[j1]temp;}}}
}int main()
{int n,s,res;freopen(input.txt,r,stdin);freopen(output.txt,w,stdout);scanf(%d %d,n,s);//从文件中取出顾客人数和服务处数量 int wait[s];int arr[n];for(int i0;in;i){scanf(%d,arr[i]);}sort(arr, n); res Greedy(wait, arr, n, s);printf(%d,res);return 0;
} 现在让我们来检验一下代码的正确性
1首先在程序所在路径下建立两个题目所需要的文本文件input.txt output.txt 2在input.txt文件中输入相关数据 3将代码运行起来下图为代码运行成功的标志 4那么接下来我们进入输出文件output.txt查看代码运行的具体效果 经过检验发现该代码实现的该实例时正确的大家可以对其他实例进行一个验证也可可以将代码自行更改增加其可行性~
