当前位置:首页 > 排序 > 正文
洛谷P7072直播获奖(CSPJ2020)
1813+

题目大意:n个分数,输入第i个分数的时候,计算并输出第i*m/100名的分数是多少?

题目描述

NOI2130 即将举行。为了增加观赏性,CCF 决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为 ,即当前排名前 的选手的最低成绩就是即时的分数线。

更具体地,若当前已评出了 个选手的成绩,则当前计划获奖人数为 ,其中 是获奖百分比, 表示对 向下取整, 表示 中较大的数。如有选手成绩相同,则所有成绩并列的选手都能获奖,因此实际获奖人数可能比计划中多。

作为评测组的技术人员,请你帮 CCF 写一个直播程序。

输入格式

第一行有两个整数 。分别代表选手总数与获奖率。
第二行有 个整数,依次代表逐一评出的选手成绩。

输出格式

只有一行,包含 个非负整数,依次代表选手成绩逐一评出后,即时的获奖分数线。相邻两个整数间用一个空格分隔。

输入输出样例

输入 #1
10 60
200 300 400 500 600 600 0 300 200 100
输出 #1
200 300 400 400 400 500 400 400 300 300
输入 #2
10 30
100 100 600 100 100 100 100 100 100 100
输出 #2
100 100 600 600 600 600 100 100 100 100

说明/提示

样例 1 解释


数据规模与约定

各测试点的 如下表:

测试点编号

对于所有测试点,每个选手的成绩均为不超过 的非负整数,获奖百分比 是一个正整数且


提示

在计算计划获奖人数时,如用浮点类型的变量(如 C/C++ 中的 floatdouble,Pascal 中的 realdoubleextended 等)存储获奖比例 ,则计算 时的结果可能为 ,也可能为 ,向下取整后的结果不确定。因此,建议仅使用整型变量,以计算出准确值。

解题思路

部分分:每次对所有数据进行排序,输出对应排名的分数。

满分:桶排序,因为分数的范围很小,统计每个分数的人数,用后缀和计算每个分数的排名。

如果用其他排序,那么插入排序应该是比较好的,比快速排序还好,因为增加一个分数前,序列已经有序。结合二分查找、内存复制移动,可能获得满分?

程序实现

桶排序

插入排序

对顶堆:需要求第k大,那么小根堆保存k个,大根堆保留剩下的分数。小根堆不足k个,大根堆传一个过去;小根堆超过k个,传一个到大根堆。

二叉排序树:可以用来练习,如果出现极端数据,会退化成$O(n^2)$。

对于相等的结点,我们可以合并在一起,一个值只用一个结点记录,这样总的结点数量不超过600,深度也就不超过600,相当于map去重、桶排序。

洛谷P7072直播获奖(CSPJ2020):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!