現在在 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 值可以使夾起的娃娃最多)
以及可以夾到的最多的娃娃個數
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 3 2 3
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
36532 | dfd8282@gmai ... (fishhh) | a014 | 426 | 2023-07-21 14:47 |