不会有人接水经常撒吧3474：练85.2 排队接水

本文介绍: 123456

【题目描述】

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

【输入】

共两行，第一行为n�(1≤n≤10001≤�≤1000)；第二行分别表示第11个人到第n�个人每人的接水时间T1�1，T2�2，…，Tn��，每个数据之间有11个空格。保证Ti��互不相同。

【输出】

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

【输入样例】

10
56 12 1 99 1000 234 33 55 99 812

【输出样例】

3 2 7 8 1 4 9 6 10 5
291.90

/*
思路  是累计时间最短，就让接水时间最短的优先接水；
排序后所有等待时间之和，等于ai* (n-i)之和； 
*/
#include<bits/stdc++.h>  
using namespace std;
int n;
struct node
{
	int x;
	int num;
};
struct node nd[1111];
int cmp(struct node nd1,struct node nd2)
{
	return nd1.x<nd2.x;
}
int main()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++)
	{
		cin>>nd[i].x;
		nd[i].num=i;
		
	}
	sort(nd+1,nd+n+1,cmp);// 排序
	for(i=1;i<=n;i++) 
	{
		cout<<nd[i].num<<" ";
	}
	cout<<endl;
	double sum=0;
	for(i=1;i<=n;i++)
	{
		sum=sum+nd[i].x*(n-i);
	}
	sum=sum/n;
	printf("%.2f",sum);
	return 0;
}

原文地址:https://blog.csdn.net/m0_74811974/article/details/135932552

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_63873.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。