n372. 6. 神仙眷侶 - 高中生程式解題系統

內容

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

輸入說明

　　輸入第一行有一個正整數 $N$ （ $2 \leq N \leq 2 \times 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
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

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

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

標籤:

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