贪心排队打水
油菜花题目
有 n个人排队到 1个水龙头处打水,第 i个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?
输入格式
第一行包含整数 n。
第二行包含 n个整数,其中第 i个整数表示第 i个人装满水桶所花费的时间 ti。
输出格式
输出一个整数,表示最小的等待时间之和。
数据范围
1≤n≤105
1≤ti≤104
输入样例
输出样例
解题思路
首先按时间大小进行排序,按样例来说,排好序后为 1,2 3, 4,5,6,7;
需要等待的时间就是16+25+34+43+52+61
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| #include<iostream> #include<bits/stdc++.h> using namespace std;
typedef long long LL; const int N =100010; int n; int t[N]; int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&t[i]); sort(t,t+n); LL res=0; for(int i=0;i<n;i++)res+=t[i]*(n-i-1); printf("%lld\n",res); return 0; }
|