給定一個長度$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
6
範測的所有區間和由小排到大為
2 3 3 4 6 6 7 9 10 12
因此第6小的是6
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||