当前位置:首页 > 离散化 > 正文
SSOJ2616数字排名
227+

题目大意:有n个数,m个询问,每次回答数x是第几大或者第x大的是哪个数。

输入

第一行:2个整数n和m

第二行:n个整数

接下来m行,每行2个数o和x,o=1请回答x(保证是n个数中的一个)是第几大,o=2请回答第x大的是哪个数,不存在第x大,输出“ERR”。

输出

q行,每行一个回答

样例输入

5 3
1 2 3 2 4
1 2
2 1
2 5

样例输出

3
4
ERR

提示

1<=o<=2;n个数,每个数的绝对值不超过20000000;5<=n、m<=200000

(10个点数据范围:5, 10, 100, 500, 1000, 5000, 10000, 50000, 100000, 150000, 200000)

解题思路

排序后去重,很容易就处理出第x大的是哪个数,我们可以预先放入p数组中。

对于回答x是第几大,我们可以在p数组中遍历查找,找到后该位置即是答案。为了提高速度,我们可以采用二分查找;为了更方便处理这个映射关系,我们还可以使用哈希表。

当然,这个只是简单的离散化,我们可以直接排序后模拟处理就行。

程序实现

排序后离散化:p数组记录去重后的数组,方便寻找第x大;x数组记录的是询问的排名或者询问的数字的排名。26行中,d[i].i < 0表示是询问的编号的相反数,因为需要回答排名,我们可以直接把排名填进去。对于每个询问,我们可以离线回答。

二分查找第x大:

哈希回答x的排名:

暴力遍历查找第x大:

更多

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2616数字排名:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter