前往
大廳
主題

ZeroJudge - f731: 老鼠的直播間 解題心得

Not In My Back Yard | 2021-04-17 00:00:18 | 巴幣 4 | 人氣 388

題目連結:


題目大意:
輸入第一列給定一正整數 n(1 ≦ n ≦ 2 × 10 ^ 5),代表有 n 個人。接著有 n 列輸入,每列給定兩正整數 a 、 b (1 ≦ a < b ≦ 10 ^ 9),代表某個人進入直播間的起始以及離開的時間點。

試問,直播間最多同時有多少人在?

注:在離開的時間點的那一「瞬間」即算作離開了直播間。所以就算有兩個人:
1 2
2 3
雖然第一個人離開時間點為 2、第二個人進入時間點也為 2,但兩人並不算同時在直播間裡。



範例輸入:
3
1 3
5 6
2 4


範例輸出:
2


解題思維:
我們將所有人的進入以及離開的時間點都拆開,不過我們需要額外將屬於「進入」、屬於「離開」的這個屬性存起來跟著原先的數字走(可以使用一個結構(Struct)存在一起),將所有數字按照大小由小到大排序。數字一樣的話,將屬於「離開」的數字排在前面。

排序過後,我們從小的數字開始看並用一個計數變數 C 計算當前人數。當遇到屬於「進入」的數字時,將 C 加 1,代表這個時間點有人進來了;反之,遇到屬於「離開」的數字時,將 C 減去 1,代表有人離開。

正因為我們已經按照了時間點的大小排序,所以變數 C 可以正確地反映出各個時間點的人數為多少。

而所求即是變數 C 在計數過程中的最大值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

瞇眼喵太郎
偶的頭⋯偶的頭哇啊啊啊啊(數學絕緣體)~~~!!!
2021-04-17 06:18:21

更多創作