a014.
夾娃娃
內容
現在在 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
公開 測資點#0 (19%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (30%): 1.0s , <1M
公開 測資點#3 (30%): 1.0s , <10M
公開 測資點#4 (1%): 1.0s , <1M
公開 測資點#0 (19%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (30%): 1.0s , <1M
公開 測資點#3 (30%): 1.0s , <10M
公開 測資點#4 (1%): 1.0s , <1M
提示 ：
出處:
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 36532 |
|
a014 | 257 | 2023-07-21 14:47 |