问题 5865 --第6题 中位数

5865: 第6题 中位数

题目描述

  先科普一下“中位数”的概念。 一个序列被从小到大排序后,排名在中间的那个数就是这个序列的“中位数”。例如,{10,40,30}的中位数是30。 如果序列的长度是偶数,我们会说两个中间元素中较小的一个是中位数。例如,{10,40,30,20}的中位数是20。 有F头奶牛(编号1至F)在参加高考,有M个科目(编号1至M)要考,第i头奶牛的第j个科目的成绩是score[i][j]。 显然,总共有F*M个成绩,我们的目标是使得:这F*M个成绩的中位数是goal。 为了完成这个目标,允许奶牛作弊,现在需要完成如下的任务: (1)确定一个最小的整数X,其中X表示必须作弊的奶牛的数量。只要修改了某头奶牛的成绩,那么该头奶牛就是作弊。 (2)在确定了最小X的前提下,还要确定一个最小的Y,其中Y表示总共需要修改多少个成绩。

输入

第一行,3个整数:F,M,goal。1 <= F, 1 <= M , F * M <= 1000。 0<=goal <= 99。 接下来有F行M列的二维数组,其中第i行第j列的整数是 score[i][j]。0<=score[i][j]<=99。

输出

一行,两个整数, X和Y。

样例输入输出

输入#1 复制
5 5 8
1 2 3 4 5
10 9 8 7 6
25 24 23 22 21
18 16 17 19 20
11 13 12 14 15 
输出#1 复制
1 5

提示

样例解释: 如果所有奶牛都不作弊,那么中位数肯定不是8。 X=1,因为只要第3头奶牛作弊就可以达到目标。 第3头奶牛的5个科目成绩都必须修改成不超过8,这样才能使得最终的中位数等于8,所以Y=5。

序号 标题 作者 发表时间 费用 订购数 操作