问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为t i n i ,1 £ £ 。共有s 处可以
提供此项服务。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时
间是n个顾客等待服务时间的总和除以n。
编程任务：
对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。
数据输入：
由文件input.txt 给出输入数据。第一行有2 个正整数n 和s，表示有n 个顾客且有s处
可以提供顾客需要的服务。接下来的1 行中，有n个正整数，表示n个顾客需要的服务时间。
结果输出:
将编程计算出的最小平均等待时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
10 2
56 12 1 99 1000 234 33 55 99 812
输出文件实例
336
贪心策略：最短服务时间优先
//多处最优服务次序问题
//input.txt
//10 2
//56 12 1 99 1000 234 33 55 99 812
//output.txt
//336
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
double greedy(vector<int> x,int s)
{
vector<int> st(s+1,0);
vector<int> su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i,j;
for(i=0;i<n;i++)
{
j=i%s; //第i的任务由第i%s处处理
st[j]+=x[i];//在第j处处理的任务运行时间之和
su[j]+=st[j];//在第j处处理的任务等待时间之和
}
double t=0;
for(i=0;i<s;i++)
t+=su[i];
t/=n;
return t;
}
int main()
{
int n,i,s,a;
vector<int> x(0);
while(cin>>n>>s,n&&s)
{
for(i=0;i<n;i++)
{
cin>>a;
x.push_back(a);
}
cout<<greedy(x,s)<<endl;
x.clear();
}
}
posted on 2012-10-19 08:37
大大木马 阅读(2629)
评论(0) 编辑 收藏 引用