zsl_ayt @ 2023-08-26 00:23:10
n, k = map(int, input().split())
q = list(map(int, input().split()))
def quick_sort(q, l, r, k):
if l == r:
return q[l]
i = l - 1
j = r + 1
x = q[(l + r) // 2]
while i < j:
i += 1
j -= 1
while q[i] < x: i += 1
while q[j] > x: j -= 1
if i < j:
q[i], q[j] = q[j], q[i]
sl = j - l + 1
if sl >= k:
return quick_sort(q, l, j, k)
else:
return quick_sort(q, j + 1, r, k - sl)
print(quick_sort(q, 0, n - 1, k + 1))by Terrible @ 2023-08-26 06:07:04
@zsl_ayt 你把数据保存到 list 里面就爆内存了，洛谷的题目没有对多数人写出的 Python 程序提供保障。
修改方法：不使用 list 保存大量数据，在此基础上要保证程序不会 TLE，那么应当使用不在 Python 层执行的语句/函数。
Python 不是让你用来写底层的——这显得非常可笑。
下面这份代码使用 numpy 来解决这个问题，numpy.array 可以替代 list。（并喜提发布时的最优解）
import numpy as np
n,k=map(int,input().split())
print(np.partition(np.fromstring(input(),dtype=np.int32,sep=' '),k)[k])洛谷只给 Python 提供了 numpy 支持，PyPy 则没有 numpy 库的支持。
by zsl_ayt @ 2023-08-26 18:42:44
@Terrible 佬，请问为什么用numpy就不会爆内存了呢，原谅我还没了解过numpy库
by Terrible @ 2023-08-26 19:55:07
@zsl_ayt
事实上
n, k = map(int, input().split())
q=input().split()提交上去就喜提两个 MLE，在 Python，一个空字符串的大小是 49 bytes，每个具体的字符占用 1 byte，64 位计算机中列表会给每个元素分配 8 bytes 的指针，列表本身占用 56 bytes。
假设 input().split() 中 input() 这个字符串在 .split() 过程中不会及时地释放内存，假设第二行数据有
已经爆空间了。
如果是 numpy 的话，首先储存的数据类型和 C语言/C++ 能够达成一致，节省空间。
Python 的 long 整数一个就要占用至少 24 bytes（取决于整数大小，越大，占用字节越多），numpy.int32 每个元素只需要 4字节，其次 numpy.array 中数据类型没有差别，不需要储存指向元素的指针，直接放元素本身即可。
而且 numpy.fromstring 过程中不会出现储存了很多很多字符串的列表，会直接生成一个新的 连续储存的 元素占用较少的 numpy.array，这就省去了过程中产生的大量无意义内存消耗。
by Terrible @ 2023-08-26 19:59:20
事实上，我们在使用 Python 的时候总是假设内存是充足的，因为近几年来的硬件发展十分迅猛，能够为很多软件上的设计不足兜底，这也是近期 Python 地位提升的最关键元素。
即便是学了 numpy 也很少有人关注其中的消耗问题，Python 得以为人宠幸的关键其一就是其脱去了程序设计种种细节形式的繁琐外衣，让人更加关注自己参与的核心过程中。
分析不管是 Python 底层还是 numpy 的程序底层，都不是一般人考虑的，因为这似乎又回到了我们厌恶的繁文缛节之中了。