某日,鄉下人要去FN家愉快地玩耍,卻發現FN睡死在家裡了。
然而頑強的鄉下人並不想要因此而露宿街頭,他很快的打電話給檸檬求救,但檸檬的記性很不好,只能大概列出可能是FN家的地點的優先順序。
鄉下人想知道,在最糟糕的情況下,自己究竟要多久才能找到FN的家?
$n$
$s_1\ s_2\ ...\ s_n$
第一行只有一個數字$n(1 \le n \le 5 \times 10^6)$代表可能是FN家的地點數量,
第二行有$n$個數字$s_i(1 \le i \le n, 1 \le s_i \le n)$代表位置為$i$的地點可能是FN家的優先順序(由小到大),當 $i$ ≠ $j$,$s_i$ ≠ $s_j$。
鄉下人初始的位置為$0$,對任兩個位置$i, j$其距離為$|i - j|$。
鄉下人需要依照$s_i$由小到大依序尋訪,不能偷吃步(即每次尋訪要先走到目前尚未走過的地點中,$s_i$為最小的地點)。
輸出一個數字代表鄉下人最多需要走多遠。
以範測1為例:
鄉下人原本的位置為0
$s_1 = 1$,位置0 => 1
$s_3 = 2$,位置1 => 3
$s_2 = 3$,位置3 => 2
總距離$|1 - 0|+ |3 - 1| + |2 - 3| = 4$
如果你用c++ 的 cin 一直吃TLE的話
可以在main函數裡面新增一行
ios_base::sync_with_stdio(false);cin.tie(0);
這叫做io優化喔 在資料量大的時候可以大幅縮短執行時間
No. | Testdata Range | Score |
---|---|---|
1 | 0~6 | 100 |