信息学奥赛一本通T1319：贪心算法 排队接水

【题目描述】有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。【输入】共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。【输出】有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)

信息学奥赛一本通T1319：排队接水

【题目描述】

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

【输入】

共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

【输出】

有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

【输入样例】

10                            
56 12 1 99 1000 234 33 55 99 812

【输出样例】

3 2 7 8 1 4 9 6 10 5
291.90

【源程序】

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct people{
    int num;
    int time;
}arr[5000];
bool cmp(people a,people b)
{
    return a.time<b.time;
}
int main()
{
    int n;
    int i;
    double time_sum=0,time_average;
    cin>>n;
    for(i=1;i<=n;i++)	
    {
        cin>>arr[i].time;
        arr[i].num=i;
    }
    sort(arr+1,arr+1+n,cmp);
    
    for(i=1;i<=n;i++)	
    {
        cout<<arr[i].num<<" ";
    	if(n-i>=1)	time_sum+=arr[i].time*(n-i);
    }    
    time_average=time_sum/n;
    
    cout<<endl;
    cout<<setiosflags(ios::fixed)<<setprecision(2);
    cout<<time_average<<endl;
        
    return 0;
}

信息学奥赛一本通T1319：贪心算法 排队接水 归属于 贪心算法，更多同类题解源程序见：贪心算法 和 排队接水

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！