贪心法习题汇总(共15页).doc

精选优质文档-倾情为你奉上贪心法习题汇总排队接水源程序名 .?（, , ）可执行文件名 输入文件名 输出文件名 【问题描述】 有个人在一个水龙头前排队接水，假如每个人接水的时间为，请编程找出这个人排队的一种顺序，使得个人的平均等待时间最小。【输入】 输入文件共两行，第一行为；第二行分别表示第个人到第个人每人的接水时间，每个数据之间有个空格。【输出】 输出文件有两行，第一行为一种排队顺序，即到的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。【样例】【算法分析】平均等待时间是每个人的等待时间之和再除以，因为是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照的自然顺序排列的，则这个问题就是求以下公式的最小值：如果用穷举的方法求解，就需要我们产生个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行!次求和以及判断，时