TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5724
  • 問題
  • P5724错乱数列
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,256m
    問題説明

    何老板给你一个长度为N的整数数列$P_1,P_2,...,P_N$,数列P是1到N的一个排列。
    何老板希望你把P调整成一个错乱数列,所谓错乱数列是指数列中不存在$P_i==i$的情况。
    你可以任意交换数列中相邻两个数,问最少交换几次,就能使P成为错乱数列。

    入力形式

    第一行,一个整数N
    第二行,\(P_1,P_2,...,P_N\)

    出力形式

    一个整数,表示最少所需交换次数

    サンプル入力 1

    5
    1 4 3 5 2

    サンプル出力 1

    2

    样例解释:
    交换1和4
    交换1和3
    就得到错乱序列4,3,1,5,2

    サンプル入力 2

    9
    1 2 4 9 5 8 7 3 6

    サンプル出力 2

    3

    ヒント

    $2≤N≤10^5$


    ソース  arc082 D - Derangement