洛谷-P1223 排队接水（贪心）

题目链接

题意：

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

思路：

标准的贪心，将接水时间最短的排在最前面即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1005;
const int mod=998244353;
const int inf=0x7fffffff;
const double pi=3.1415926535;
using namespace std;
signed main()
{
    int i,n,a[N],b[N],f;
    double s=0;
    cin>>n;
    for(i=1;i<=n;i++)
    { 
        cin>>a[i];
        b[i]=i;
    }
    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]<<" ";
    }
    cout<<endl;
    for(i=1;i<=n;i++)
    {
        a[i]*=(n-i);
        s+=a[i];
    }
    printf("%.2lf",s/n);
    return 0;
}

本文地址：https://blog.csdn.net/ACkingdom/article/details/107193162