n372. 6. 神仙眷侶
標籤 : 最近點對
通過比率 : 4人/7人 ( 57% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-03 14:51

內容

  我與他(她),究竟是天作之合,還是這不過是一時情竇初開的衝動魯莽...
  喵老師在新莊高中教書二十年了,早就見慣了學生們感情世界的悲歡離合,一對情侶可否攜手終老,從來就不是一時熱血沸騰所能下定論的。
  喵老師發現,兩人能否長相廝守,可以藉由學期中與期末的班級座位看出些端倪,如果兩人在兩次的座位中距離總和是全班當中最小的,那他們將是班上的神仙眷侶。
  老師想將這個任務交給你,給你期中、期末班上的兩份座位表,請你寫一支程式,計算班上神仙眷侶的兩次座位距離總和,以及班上有幾對神仙眷侶(註:一個人可以跟不只一人成為神仙眷侶)。為了方便計算,班上的座位呈現一直排,一個座位表 $p$ 會有 $N$ 個正整數 $p_1\sim p_N$,$p_i$ 代表坐在第 $i$ 個位置的學生的座號。
  輸入兩份座位表 $p0, p1$,請你找到一對座號 $a, b$($a<b$),$p0_{i_0}=p1_{i_1}=a$,$p0_{j_0}=p1_{j_1}=b$,使得 $|i_0-j_0|+|i_1-j_1|$ 最小,輸出此最小值,並輸出有多少對 $a, b$ 符合此最小值。

輸入說明

  輸入第一行有一個正整數 $N$($2\le N\le 2×10^5$),代表班級人數,接下來兩行各有 $N$ 個正整數 $1\sim N$,代表一份座位表。測資保證每份座位表的座號不重複。

輸出說明

  輸出兩個整數 $d, p$,以空白隔開,代表班上神仙眷侶兩次座位的距離總和為 $d$,並且班上有 $p$ 對這樣的情侶。

範例輸入 #1
7
1 2 3 4 5 6 7
3 6 1 2 4 7 5
範例輸出 #1
2 1
範例輸入 #2
5
1 3 2 5 4
5 3 4 2 1
範例輸出 #2
3 5
測資資訊:
記憶體限制: 512 MB
提示 :

  範例輸入 #1 有 $1$ 對神仙眷侶 $(1,2)$,其座位距離為 $1+1=2$。
  範例輸入 #2 有 $5$ 對神仙眷侶分別為 $(1,2)$、$(2,3)$、$(2,4)$、$(3,5)$、$(4,5)$。

本題共有 $4$ 個子題,每個子題有多筆測資。
第一子題: $N\le 3$,全部解出可得 $10$ 分。
第二子題: $N\le 100$,全部解出可得 $10$ 分。
第三子題: $N\le 2\times 10^4$,全部解出可得 $30$ 分。
第四子題: $N\le 2\times 10^5$,全部解出可得 $50$ 分。

標籤:
最近點對
出處:
112學年度新北新莊高中校內資訊學科能力競賽 [管理者: liaoweichen1 ... (M_SQRT) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」