TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • 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