问题 1336. -- 区间第K大

1336: 区间第K大

时间限制:1000 ms 内存限制:128 MB
提交:29 解决:14
[ 提交][ 状态][ 讨论版]

题目描述

tsy和zxy被誉为时空管理者,他们一直追求着最优秀的算法来做题，有一天汪聚聚给大家留了一道练习题，并告诉大家如果有人能解决，那么他会女装，题意是这样的:给定一个序列，定义一段连续区间的和为这段区间的价值，让你求这个序列中第K的区间价值是多少？为了让汪聚聚圆了女装梦，大家都纷纷想解决这道题，然而菜鸡qko只会比较蠢的方法以至于被汪聚聚批评，希望你能像聪明的tsy和zxy一样，用比较优秀的方法解决这道题！

输入

单组数据

第一行一个数字N代表数列个数（1 <= N <= 1e5）

之后N个数字代表各个元素(0 <= A[i] <= 1e9)

之后一行一个数字K代表第K大(1 <= K <= N * (N + 1) / 2)

输出

一个数字代表第K大的数列和

样例输入

5 1 1 1 1 1 2

样例输出

4

提示

来源

火辣鸡不会include

[ 提交][ 状态][ 讨论版]
Baidu
map