区间第K大-j9国际集团直营

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

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