a014. 夾娃娃
標籤 : BIT ST
通過比率 : 131人/220人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 18:33

內容

現在在 1D 空間內夾娃娃,知道娃娃的位置,而這個遊戲很不公平

只要是在夾娃娃機的夾子範圍內,都可以夾起來,這簡直太不太平了

對於不會計算的小光,簡直是不公平的遊戲,請你幫忙解決這不公平的遊戲

 

遊戲規則:

假設現在夾娃娃機可以看成一個直線座標系,

夾娃娃機的機身範圍 X∈[0,+∞),

裡面有 N 個娃娃,

娃娃分布範圍 X∈[1,100000] ,

而每一個娃娃都位在 X1 ∈ [A,B] ,

若夾子寬度為 Y ,夾子的左端坐標為 C , C ∈ N+

則夾子可以夾起 X2 ∈ [C, C+Y] 這個範圍內的娃娃,

只要 X1 ⊆ X2 ,則娃娃可以被夾起,

Y , A , B  ∈ N+

輸入說明

有多筆測資

每組的第一行有兩個整數 N  Y  ( 1 ≦ N Y ≦ 3,0000 )
接下來會有 N 行,每行上有兩個正整數 A B ( 1 ≦ A ≦ B ≦ 10,0000 )

輸出說明

請輸出最佳的夾取地點的個數(有幾個 C 值可以使夾起的娃娃最多)

以及可以夾到的最多的娃娃個數

範例輸入 #1
5 4
1 3
2 5
3 6
2 6
5 7
5 4
1 3
2 5
3 6
2 5 
5 7
範例輸出 #1
1 3
2 3
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
BIT ST
出處:
[管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
36532 dfd8282@gmai ... (fishhh) a014
解題報告
426 2023-07-21 14:47