P1223 排队接水 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

考点：贪心算法

思路：很简单，快的先接水即可，要注意重复项

代码:

#include<iostream>
#include<algorithm>
using namespace std;int arr[1000005];//排序后
int arr1[1000005];//原数组
int arr2[1000005];//等待时间
bool flag[1000005];//等待时间int main()
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> arr[i];}for (int i = 0; i < n; i++){arr1[i] = arr[i];}sort(arr, arr + n);//arr排序double sum = 0;//56 12 1 99 1000 234 33 55 99 812 j//1 12 33 55 56 99 99 234 812 1000 ifor (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (arr[i] == arr1[j]){if (flag[j])//选过的不再选continue;cout << j + 1 << " ";flag[j] = 1;}}}for (int i = 1; i < n; i++){arr2[i] = arr2[i - 1] + arr[i - 1];//等待时间是前一个人等待时间加上前一个人接水时间}for (int i = 0; i < n; i++){sum += arr2[i];}double N = n;printf("\n%.2lf", sum / n);return 0;
}