「RQNOJ255」排队接水

2013年12月19日2,5250

题目描述

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

注意：若两个人的等待时间相同，则序号小的优先。

输入格式第一行为n。

第二行到最后一行中,共有n个整数,

分别表示第一个人到第n个人每人的接水时间t[1],t[2],t[3],t[4],……t[n]，每个数据之间有一个空格或换行。

数据范围: 0<n<=900, 0<t<=1000

输出格式共两行，第一行为一种排队顺序，即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<cstdio>
#include<algorithm>
using namespace std;
struct data{
    int t,num;
}a[901];
int gz(const data &a,const data &b)
{
	if(a.t>b.t||a.t==b.t&&a.num>b.num)return 0;
	return 1;
}
int main()
{
	int n;
	float ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	   cin>>a[i].t;
	   a[i].num=i;
}
    sort(a+1,a+n+1,gz);
    for(int i=1;i<=n;i++)
    {
       cout<<a[i].num;
       ans+=a[i].t*(n-i);
       if(i!=n)cout<<' ';
    }
    cout<<endl;
    printf("%.2f",ans/n);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct data{

int t,num;

}a[901];

int gz(const data &a,const data &b)

{

if(a.t>b.t||a.t==b.t&&a.num>b.num)return 0;

return 1;

}

int main()

{

int n;

float ans=0;

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>a[i].t;

a[i].num=i;

}

sort(a+1,a+n+1,gz);

for(int i=1;i<=n;i++)

{

cout<<a[i].num;

ans+=a[i].t*(n-i);

if(i!=n)cout<<' ';

}

cout<<endl;

printf("%.2f",ans/n);

return 0;

}

« 活动安排问题「JoyOI1090」母舰 »

hzwer.com _ Home | http://hzwer.com

「RQNOJ255」排队接水

分类目录

热门文章

Myfriends

近期评论