C. B-1 建堆的时间复杂度

    传统题 1000ms 256MiB

B-1 建堆的时间复杂度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

有一道著名的企业面试题是这样的:将 nn 个整数存在一维数组里,然后建立一个最小堆,最快算法的时间复杂度是多少?答案是 O(n)O(n) 。但是有非常多的人答错!下面给出所有面试者的答案,请你统计一下这道题各项选择的人数和题目的正答率。

麻烦的是,由于使用了随机组卷,题目的 4 个选项 A、B、C、D 是随机打乱的,所以这个统计还略复杂。我们假设系统里将每一份卷子上选项出现的顺序记为数字 1 到 4 的一个排列。例如 3142 表示这份卷子上的选项 A 对应原始题目的选项 C,这份卷子上的选项 B 对应原始题目的选项 A,这份卷子上的选项 C 对应原始题目的选项 D,这份卷子上的选项 C 对应原始题目的选项 B。如果原始题目中的正确答案是单选 A,则这份卷子的主人如果单选了卷面上的 B 就得到满分。

输入格式

输入首先在第一行给出原始题目的正确答案X(为ABCD四个大写字母之一)和一个正整数 mm1000\le 1000 ),是面试者人数。二者以空格分隔。

随后 mm 行,每行给出一张卷子的答案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

PAT2025春季重现赛

未参加
状态
已结束
规则
IOI
题目
11
开始于
2025-7-20 14:00
结束于
2025-7-20 17:30
持续时间
3.5 小时
主持人
参赛人数
46