a121. 第K小區間和 - 旦旦解題農場

內容

給定一個長度 $N$ 的陣列 $A_i$ ，一個區間的定義為連續的元素，也就是對於所有 $1\le l\le r\le N$ 都代表著一個區間 $A_l,A_{l+1},...,A_{r-1},A_r$ ，一共有 $\frac{N(N+1)}{2}$ 個相異區間，而區間和則是區間內元素的總和。若將所有的區間和排序，請問第 $K$ 小的值是多少?

輸入說明

第一行有兩個正整數 $N,K$ 。

第二行有 $N$ 個正整數 $A_i$ 。

20%測資 $N\le 3000$

80%測資 $N\le 10^5$

100%測資 $N\le 10^6,A_i\le 10^9,K\le \frac{N(N+1)}{2}$

輸出說明

輸出一個數字代表第 $K$ 小區間和。

範例輸入

4 6
2 4 3 3

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 0.5s , <1M
公開測資點#1 (20%): 0.5s , <1M
公開測資點#2 (20%): 0.5s , <1M
公開測資點#3 (20%): 0.5s , <1M
公開測資點#4 (20%): 0.5s , <10M

提示：

範測的所有區間和由小排到大為
2 3 3 4 6 6 7 9 10 12
因此第6小的是6

標籤:

出處:

[管理者：

giver (垃圾)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」