我與他(她),究竟是天作之合,還是這不過是一時情竇初開的衝動魯莽...
喵老師在新莊高中教書二十年了,早就見慣了學生們感情世界的悲歡離合,一對情侶可否攜手終老,從來就不是一時熱血沸騰所能下定論的。
喵老師發現,兩人能否長相廝守,可以藉由學期中與期末的班級座位看出些端倪,如果兩人在兩次的座位中距離總和是全班當中最小的,那他們將是班上的神仙眷侶。
老師想將這個任務交給你,給你期中、期末班上的兩份座位表,請你寫一支程式,計算班上神仙眷侶的兩次座位距離總和,以及班上有幾對神仙眷侶(註:一個人可以跟不只一人成為神仙眷侶)。為了方便計算,班上的座位呈現一直排,一個座位表 $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$ 對這樣的情侶。
7 1 2 3 4 5 6 7 3 6 1 2 4 7 5
2 1
5 1 3 2 5 4 5 3 4 2 1
3 5
範例輸入 #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$ 分。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|