说明
本系列题目为 2020 年为计算机试验班 91 开设的 COMP350105 “算法设计与分析” 课程之期末实验题目。 本题目的规定与要求不代表课程实验中的要求,本题目的得分不代表实验得分,本题目的数据也不代表课程期末实验的测试方式。 而且在本 OJ 上的程序正确性、效率性要求往往高于课程得分要求,但代码可读性、程序思想要求却低于课程得分要求。本题目为大家提供严谨的测试,请各位酌情根据自己能力解答。
题面原文
设有 个互不相同的元素 ,每个元素 带有 一个权值 ,且 。若元素 满足 且 ,则称元素 为 的带权中位数。请编写一个算法,能够在最坏情况下用 时间找出 个元素的带权中位数。
本题的约定
为浮点数。带权中位数即满足上述条件的元素。
交互
为了严格控制该题的运行效率,本题采用交互方式进行。在开始交互之前,您的程序会得到序列的长度和第 个元素的权值 。交互的每一步,你的程序可以输出 q a b
询问两个元素 ,交互程序返回这两个元素的大小关系。
本题限制了交互时 q
询问的次数,如果您的程序询问次数超过 ,您的程序将被视为不通过。
在每次输出后,请刷新缓冲区,否则可能收到 idleness exceeded
错误,刷新缓冲区的方法如下:
fflush(stdout); // c++
System.out.flush(); // java
stdout.flush() # python
flush(output) // pascal