P1223 排队接水（贪心）

题目描述

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

输入格式

第一行为一个整数 𝑛。

第二行 𝑛n 个整数，第 𝑖个整数 𝑇𝑖表示第 𝑖个人的接水时间 𝑇𝑖​。

输出格式

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

输入输出样例

输入 #1复制

10 
56 12 1 99 1000 234 33 55 99 812

输出 #1复制

3 2 7 8 1 4 9 6 10 5
291.90

说明/提示e

1≤𝑛≤1000，1≤𝑡𝑖≤10e6，不保证 𝑡𝑖​ 不重复。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;struct water{       //这边用结构体来使程序更加的简洁
int time=0,number=0;}p[1001];bool cmp(water a,water b){   //如果时间相同把小的序列放前面，方便后面算平均值
if(a.time!=b.time)   return a.time<b.time;return a.number<b.number;
}
typedef long long LL;    //加不加都无所谓
int main(){int n;LL sum=0;double average=0;
cin>>n;
for(int i=1;i<=n;i++){cin>>p[i].time;p[i].number=i;
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++){cout<<p[i].number<<" ";
sum+=i*p[n-i].time;    //这边人打完水就走，然后等待时间是每个人的
}
printf("\n");
average=1.0*sum/n;  
printf("%.2lf",average);
return 0;
}

后面会继续更新二分法，分治，递归，前缀和，暴力枚举还有模拟内容敬请期待

12.8