B-1 建堆的时间复杂度
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
有一道著名的企业面试题是这样的:将 个整数存在一维数组里,然后建立一个最小堆,最快算法的时间复杂度是多少?答案是 。但是有非常多的人答错!下面给出所有面试者的答案,请你统计一下这道题各项选择的人数和题目的正答率。
麻烦的是,由于使用了随机组卷,题目的 4 个选项 A、B、C、D 是随机打乱的,所以这个统计还略复杂。我们假设系统里将每一份卷子上选项出现的顺序记为数字 1 到 4 的一个排列。例如 3142 表示这份卷子上的选项 A 对应原始题目的选项 C,这份卷子上的选项 B 对应原始题目的选项 A,这份卷子上的选项 C 对应原始题目的选项 D,这份卷子上的选项 C 对应原始题目的选项 B。如果原始题目中的正确答案是单选 A,则这份卷子的主人如果单选了卷面上的 B 就得到满分。
输入格式
输入首先在第一行给出原始题目的正确答案X
(为ABCD
四个大写字母之一)和一个正整数 ( ),是面试者人数。二者以空格分隔。
随后 行,每行给出一张卷子的答案Y
和该卷子的随机顺序(即数字 1 到 4 的一个排列),其间以空格分隔。
输出格式
在一行中输出 5 项,依次为选择了原始题目中 A、B、C、D 四个选项的人数、以及此题的正答率,其间以空格分隔,行首尾不得有多余空格。其中正答率的输出格式为n/m
,其中n
是选择了正确答案的人数,m
是总人数。
题目示例数据
C 5
C 1 2 3 4
C 3 1 4 2
B 4 3 2 1
A 2 1 4 3
D 1 3 2 4
0 1 2 2 2/5