小编Bij*_*jan的帖子

问题陈述

我一次给出一个非常大的数字列表,我需要打印" 中位数 ".

更清楚的是,可以有" 125,000,000 "数字,并保证每个数字小于" 1.e + 18 ".

这是一场比赛,因此有内存限制(20 MB顶部)和时间限制(5秒顶部).

" 中位数 "是排序数字中间的数字.
例如,如果这是数字列表:

23
8
16
42
15
4
108

排序后的数字:

1) 4
2) 8
3) 15
4) 16
5) 23
6) 42
7) 108

" 中位数 "将是16;

所以我在互联网上搜索它,但我找不到任何通过这些限制的答案.

途径

我的方法是获取所有数字,将它们保存在文本文件中,对它们进行排序,然后得到" 中位数 ".

思路

1. 我知道我可以从文件中读取所有数字并将它们放在矢量中,然后轻松地对它们进行排序.
   但这将超过内存限制.
   
   
2. 所以当我把它们放在文本文件中时,我提出了这个想法来对数字进行排序.
   这就像有一个循环,从控制台获取下一个数字后读取文件(逐行),当它到达正确的位置时,在那里插入数字,不接触其他数字.
   但问题是我不能在文本文件的中间插入一行,因为它会覆盖其他数字.
   
   
3. 所以我创建了两个文件,其中一个已经输入了数字,另一个读取了第一个文件,并将其自身的数字复制到正确的位置,然后插入最后给定的数字,然后继续复制剩余的数字.
   但它花费了太多时间,因此超出了时间限制.
   

请求

因此,我想要优化其中一个想法,以便通过限制或通过这些限制的任何新想法.

偏爱

我更喜欢使用第二个想法,因为与其他两个不同,它通过限制,但我不能这样做,因为我不知道如何在文本文件的中间插入一行.因此,如果我了解这一点,其余的过程将非常简单.

试图解决方案

这是一个接收数字的函数,通过读取文件,找到它的最佳位置并将其放在那里.
事实上,它代表了我的第三个想法. …