排队接水水水水水水

排队接水

题目链接

题意

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

算法一：冒泡排序

时间复杂度

$ O(n^2)

代码

 #include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    //freopen("t1.in","r",stdin);
    //freopen("t1.out","w",stdout);
    //cout<<fixed<<setprecision()<<;
    int i,n,a[1005],b[1005],f;//定义数组，一个赋值，一个记录序号 
    double s=0;//结果要是浮点数形式 
    cin>>n;//输入 
    for(i=0;i<n;i++){ 
        cin>>a[i];//输入
        b[i]=i+1;//如果i为0，要加一 
    }
    for(i=0;i<n;i++){
        for(int j=n-1;j>0;j--){
            if(a[j]<a[j-1]){
                swap(a[j],a[j-1]);//冒泡大法！！！ 
                swap(b[j],b[j-1]);//注意，这里要同时变换 
            }
        }
    }
    for(i=0;i<n;i++){
        cout<<b[i]<<' ';//数出序号 
    }
    for(i=0;i<n;i++){//这里有个公式，s=a1*n+a2*(n-1)+a3*(n-2)+a4*(n-3)……一直到 an 
        a[i]*=(n-i-1);
        s+=a[i];
    }
    cout<<endl;//换行 
    s/=n;
    cout<<fixed<<setprecision(2)<<s;//保留两位输出 
    return 0;//庄严地结束程序 
}