洛谷P1223

发布于 26 天前  10 次阅读


出题人考语文系列。
感谢sqy的解答(语文)。
思路:贪心一波,考虑一个问题:啥时候平均等待时间最小?
所以,平均等待时间是啥?
答:就是每个人的等待时间加起来,除以人数。
那么答案很显然了:让前面的人等待时间尽可能少(这样的话每个人等待的时间都会少,因为一个人接水的时候后面的人都在等),然后累加/n。
Code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
#define maxn 1001
using namespace std;
struct Peo{
    int t,num;
}a[maxn];
int n;
double res=0;
inline bool cmp(Peo x,Peo y){
    return x.t<y.t;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].t;
        a[i].num=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        cout<<a[i].num<<" ";
        res+=a[i].t*(n-i);
    }
    cout<<endl; 
    printf("%.2lf\n",res/n);
    return 0;
}

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。