#include<bits/stdc++.h>
int n;
long long ans;
struct node
{
    int id,t;
}a[1001];
bool cmp(node x,node y)
{
    return x.t<y.t;
}
int main()
{
    std::cin>>n;
    for(int i=1;i<=n;i+=1)
    {
        std::cin>>a[i].t;
        a[i].id=i;
    }
    std::sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i+=1)
    {
        std::cout<<a[i].id<<' ';
        ans+=(n-i)*a[i].t;
    }
    printf("\n%.2f",(double)ans/n);
}

#include <iostream>
#include <cstdio>
#include <algorithm>
struct node{int id,t;}a[1005];
int yasuo(node a,node b){
    return a.t<b.t;}
int main(){
    int n;double ans=0; std::cin>>n;
    for(int i=1;i<=n;i++){
        std::cin>>a[i].t; a[i].id=i;}
    std::sort(a+1,a+n+1,yasuo);
    for(int i=1;i<=n;i++){
        std::cout<<a[i].id<<" "; ans+=a[i].t*(n-i);}
    printf("\n%.2f",ans/n); return 0;}

题目描述

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

输入格式

第一行为一个整数 n。

第二行 n 个整数，第 i 个整数 Ti​ 表示第 i 个人的等待时间 Ti​。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

思路

1.按照题目要求，找到排队接水最短的平均等待时间， 平均等待时间=所有人等待的时间/n，n为定值，那么 总等待时间越短，即平均等待时间越短。

2. 现在分析等待时间，第一个人是不用排队的，所以没 有等待时间，第一个人的接水时间为t1的话，第二个 人的等待时间为t1，第二个人的接水时间为t2的话，第 三个人的等待时间为t1+t2,依次类推，最后一个人的等 待时间为t1+t2+..+t(n-1)，将所有人的等待时间相加 后，s=（n-1)t1+(n-2)t2+..+1t(n-1)+0tn; 得出公式后可以猜想，t1的系数最大，那么t1最小的时 候，才会使这个值不会那么大，由此推断，t1到tn应该 是从小到大排序的，这样结果才是最小的
3. 为了验证想法，利用反证法，假设最佳方案并不是由 小到大排序的，那么当编号itj，意思为第i 号的接水时间大于第j位同学，那么总时间应该为s1 =ati+btj，其中a>b，因为编号越前的系数越大，现 在计算如果第j位同学在前的时间为s2=atj+bti，将s1 和s2相减后得到结果为（a-b)*(ti-tj),两项均大于0，所以 方案2用时更短，尤其推翻方案1不是最优解
4. 接下来将输入的数据排序，并且乘上对应的系数便可 求得结果

题解

#include<bits/stdc++.h>   // by hetao5487227
using namespace std;
struct student{
    int num;
    int time;
}a[1005];   //学生排队接水的结构体数组，num为编号，time为时间 
 
bool cmp(student x,student y)
{
    if(x.time!=y.time)   //如果时间不相等的话，返回用时较短者 
    return x.time<y.time;
    return x.num<y.num;   //如果时间相等的话，返回编号小的学生 
}
int main()
{
    int n;
    double sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].time;
        a[i].num=i;
    }
 
    sort(a+1,a+n+1,cmp);   //进行排序
 
    for(int i=1;i<=n;i++)
    {
        cout<<a[i].num<<" ";   //依次输出编号 
        sum=sum+(n-i)*a[i].time;   //累加等待时间 
    } 
 
    cout<<endl;
    printf("%.2lf",sum/n);
    return 0;
}