Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5926 --第5题 排队打饭
5926: 第5题 排队打饭
警告!
题目
状态
题解(4)
题目描述
每天中午下课铃一打,同学们为了能尽早吃上饭,不要排那么长时间的队,都像狼一样冲向食堂,校领导看到这种情况很是担忧,因为学生们这样狂奔很危险,所以就要求必须等所有同学都来到食堂才能开始打饭,并且把排队打饭的顺序固定下来,这样谁都不用抢了。 学校里一共有N(1<=N<=100)个学生,每个学生打饭所需时间也是已知的,为了不让学生排队等得心烦,要求设计一个排队顺序使得所有学生的等待时间之和最小,等待时间为从开始排队到开始打饭所需的时间,所以第一个学生的等待时间为0。 为了给同学们新鲜感,领导想在保证等待时间之和最小的情况下尽可能多地改变排队顺序,所以想知道一共有多少种排队顺序?你能帮忙吗?
输入
第一行输入一个整数N(1<=N<=100),表示学生人数。 第二行输入N个正整数(在1到100之间),中间用空格隔开,表示每个学生打饭所需要的时间。
输出
一行输出两个整数,第一个数表示最小的等待时间之和,第二个整数表示在保证等待时间之和最小的前提下的排队方案数,第二个数可能很大,所以输出方案总数对2011的余数。
样例输入输出
输入#1
复制
4 1 2 1 2
输出#1
复制
7 4
提示
样例解释: 有4种排队方案分别是1 3 2 4、3 1 2 4、1 3 4 2、3 1 4 2,等待时间为7。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及/提高-
标签
贪心
点击显示
if ($pr_flag) { ?>
递交数
183
已通过
50
} ;?>
通过率
28%
时间限制
1 秒
内存限制
128 MB
来源
2017大沥镇初中
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和