c177: 合唱隊面試
標籤 :
通過比率 : 80% (32 人 / 40 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-03-29 20:26

內容 :

有 n 個人去面試合唱隊,每個人的身高是 h[i] (0 <= h[i] <= 200)。

合唱隊競選名額是 m 人。為了隊形好看,合唱隊中任何兩個人的身高只差不得超過 k 。面試官提前獲知了面試人的名單以及他們的身高,他希望盡早結束面試。如果只從前 p 個人中就能挑選出 m 個人組成一個合法的合唱隊,那麼面試官就會告知後面等待面試的人不必面試了。

畢竟面試官真是太偷懶了,想早點下班,所以他想知道最少面試多少個人就可以下班啦。也就是說,我們想知道最小的 p 。

輸入說明

第一行有三個正整數 n,m,k,意義見題目描述。

第二行有 n 個以空格隔開的數字 h[i] ,表示每個人的身高。

輸出說明

輸出一行,即最小的 p 。如果很不幸,就算在所有 n 個人中挑選 m 個人也無法組建一個合唱隊,那麼輸出 Impossible 。

範例輸入
5 3 2
1 2 3 4 5
範例輸出
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 0.5s , <1M
公開 測資點#1 (10%): 0.5s , <1M
公開 測資點#2 (10%): 0.5s , <1M
公開 測資點#3 (10%): 0.5s , <1M
公開 測資點#4 (10%): 0.5s , <1M
公開 測資點#5 (10%): 0.5s , <1M
公開 測資點#6 (10%): 0.5s , <1M
公開 測資點#7 (10%): 0.5s , <1M
公開 測資點#8 (10%): 0.5s , <1M
公開 測資點#9 (10%): 0.5s , <1M
提示 :

對於 60% 的數據,n <= 2000。
對於 100% 的數據,1 <= m <= n <= 10000,0 <= k <= 100。

感謝 lavender730 提供測資!

標籤:
出處:
2017清華大學考研機試 [編輯: liouzhou_101 (王启圣) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」