k572. pC. 關於冷氣調溫這件事
Tags : 前綴和 差分 離散化
Accepted rate : 29人/33人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-05-19 02:31

Content

每個人都會有自己覺得舒適的溫度範圍,
但當所有人都處在同個空間時,只能夠盡可能將空調設定為最多人所能接受的適宜溫度。

如果有多個最多人所能接受的適宜溫度,
為了節能省電,則會選擇溫度最大者。

舉例來說,假設有 3 個人,
喜歡的溫度範圍分別為 [19度 ~ 25度], [23度 ~ 26度], [18度 ~ 20度]

溫度181920212223242526
編號0 AAAAAAA 
編號1     BBBB
編號2CCC      

 

可以注意到,19、20、23、24、25 這五個溫度都有最多人(此題為兩人)喜歡,
而 25 度是其中最大者,因此最後會將冷氣設定為 25 度。

給定 N 個人,與各自喜歡的溫度區間 [L : R]
請找出最多人喜歡的溫度,當同時有多個時則印出最大者。

Input

第一行有一個正整數 N,代表總人數
1 ≤ N ≤ 100

接著有 N 行,每行有兩個整數 L 和 R,
代表喜歡的溫度區間 [L, R]
-109 ≤ L ≤ R ≤ 109

Output

最多人喜歡的溫度,
當同時有多個時,則印出最大者。

Sample Input #1
3
19 25
23 26
18 20
Sample Output #1
25
Sample Input #2
2
-1000000000 999999995
-999999995 1000000000
Sample Output #2
999999995
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1K
公開 測資點#15 (5%): 2.0s , <1K
公開 測資點#16 (5%): 2.0s , <1K
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
Hint :

20%:16 ≤ L ≤ R ≤ 30
10%:N = 2
10%:N = 3

60%:無特別限制 

Tags:
前綴和 差分 離散化
出處:
112學年度hgsh校內賽 [管理者: mushroom.cs9 ... (mushroom) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
35250 mushroom.cs9 ... (mushroom) k572
題解
222 2023-05-19 02:37