排列

[编程题]排列

热度指数：695 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

妞妞得到一个(1~n)的排列p₁, p₂, p₃,...,p_n, 听村里的老人牛牛说如果让这个排列变为:

对于所有的1 <= i <= n, 都满足p_i ≠ i, 就可以获得Google Girl Hackathon的入场券。

妞妞仅允许的操作是: 交换排列中两个相邻的元素, 并且妞妞允许做这个操作任意次。

但是Google Girl Hackathon就快要开始了, 妞妞希望做最少的操作就使排列满足要求, 妞妞希望你能帮助她。

输入描述:

输入包括两行, 第一行包括一个正整数n(2 <= n <= 10^5), 表示排列的长度和范围。
第二行包括n个正整数p₁, p₂, p₃,...,p_n, 即妞妞得到的排列, 保证是一个1~n的排列。

输出描述:

输出一个整数, 表示妞妞需要的操作次数。

示例1

输入

5
1 4 3 5 2

输出

算法知识视频讲解

Java

詆調壹點

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            boolean[] arr = new boolean[n];
            for (int i = 1; i <= n; i ++) {
                if(sc.nextInt() == i) arr[i - 1] = true;
            }
            int count = 0;
            int i = 0;
            while (i < n) {
                if(arr[i]) {
                    count ++;
                    i += 2;
                } else i ++;
            }
            System.out.println(count);
        }
    }
}

编辑于 2018-03-20 13:53:09 回复(0)