b315. 紅圓茵可的考驗
Tags :
Accepted rate : 66人/81人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-09-25 12:37

Content
身為魔法師的你,想讓自己變得更強大,於是前來膜拜紅圓茵可,同時想請教他學習魔法的秘訣。經過日復一日的嘗試,你終於通過了柏油路,並且來到茵可家。「看在你這麼努力的份上,我就稍微指導你一下吧。」茵可說道。「所謂魔法,跟程式設計很像,就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起,就會變成強大的魔法(像是防護罩就是控制空氣分子的移動,並使其重新排列成為堅固的結構,達到防禦的效果。)。所以說,腦中運算的能力是很重要的。」語畢,茵可大大丟給你一個題目:

給你N個數字,挑出其中兩個數字可以得到一個數字差(非負),而N個數字會有N*(N-1)/2個數字差,問第K大數字差是多少?
如範例輸入,數字差有6個,分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8),其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

Input
第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資
1. N<=10,K<=N*(N-1)/2
2. N<=1,000,K<=N*(N-1)/2
3. N<=10,000,K<=10,000
4. N<=100,000,K<=100,000
5. N<=100,000,K<=1,000,000,000

Output
輸出第K大數字差

Sample Input #1
4 5
1 5 8 10
Sample Output #1
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
出處:
103學年度板橋高中校內資訊學科能力競賽(五) [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」