本文主要是介绍HOJ1941 超市收银问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
超市收银问题
L最近在工大外面开了一个小超市。由于该超市物美价廉,且服务态度热情,因此刚开业就十分火爆。可是,这个超市目前只有两个收银台,以至于最近经常有顾客抱怨等待交款的时间太长。
这个超市目前暂时没有办法增加新的收银台,因此,L想通过别的办法缓解这个问题。现在,假设有N个顾客在等待交款。显然,前两个顾客可以马上得到服务,而后面的就得排队等候。L想重新调整一下两支队伍,使得这N个顾客们的平均等待时间最小。假设这N个顾客交完费之前不会来新的顾客。请你帮他完成这个任务。
Input
本题有多组数据。每组数据占两行,第一行是一个正整数N(N <= 1000),代表等待交款的顾客的数量。第二行有N个正整数,代表这N个顾客交款所需时间(这可以由顾客们购买的东西的数量推出),单位是秒。
Output
对于每组数据,请把这N个顾客安排到这两个队列中,使得这N个顾客的平均等待时间最小。一个顾客的等待时间指顾客从排队开始,到开始交款所需时间,而不算交款的时间。你只需输出一个浮点数,代表这些顾客的平均等待时间。单位是秒,精确到小数点后3位。
Sample Input
6 16 15 12 14 13 22Sample Output
13.167
#include <cstdio>
#include <algorithm>int q[1010], n, ans;int main(){while(~scanf("%d", &n)){for(int i = 0; i < n; i++)scanf("%d", q + i);std::sort(q, q + n);ans = 0;int t = (n + 1) / 2;for(int i = 0; i < n; i += 2)ans += (--t) * q[i];t = n - (n+1) / 2;for(int i = 1; i < n; i += 2)ans += (--t) * q[i];printf("%.3lf\n", ans * 1.0 / n);}return 0;
}
这篇关于HOJ1941 超市收银问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!