我要招人

去企业版

首页 > 试题广场 >

排列

[编程题]排列

热度指数：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

输出

算法知识视频讲解

霍七

本套6道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

牛客网上的其他题目解答也在持续更新。

【题解】如果有一个pi=i或一对pi=i并且pi+1=i+1，则需要一次交换。

#include 
using namespace std;
int main()
{
    int n; cin >> n;
    int equal = 0, count = 0, data;
    while (count < n) {
        cin >> data;
        if (data == ++count) {
            if (count != n) cin >> data;
            count++; equal++;
        }
    }
    cout << equal;
    return 0;
}

编辑于 2017-12-26 15:01:01 回复(0)

pipi_wei

这个题有bug，比如当输入的组合为1 1 2，输出应该为2，但是输入用例并没有考虑。

发表于 2018-05-20 15:38:14 回复(1)

Reyzal

本套试题AC代码在https://github.com/ReyzalX/nowcoder查看

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int result = 0;
    int i = 0;
    while(i < n)
    {
        int num;
        cin >> num;
        //如果当前数等于i 则次数+1
        //如果下面一个数等于i+1 则次数也是+1
        if (num == i+1) {
            if (i < n) {
                i++;
                cin >> num;
            }
            result++;
        }
        i++;
    }
    cout << result << endl;
    return 0;
}

发表于 2018-03-26 01:05:41 回复(1)

龍傲人间

#include <iostream>

using namespace std;

int main()
{
    bool isswap = 0;
    int size, pi, i=1, num=0;
    cin >> size;
    while(i <= size)
    {
        cin >> pi;
        if(pi == i && !isswap)
        {
            ++num;
            isswap = 1;
        }else{
            isswap = 0;
        }
        ++i;
    }
    cout << num;
    return 0;
}

发表于 2017-12-26 16:09:51 回复(0)

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)

迷雾重重

def lll (array):
    count = 0
    for i in range(len(array) - 1):
        if i + 1 == array[i]:
            array[i],array[i + 1] = array[i + 1],array[i]
            count += 1
    return count
if __name__ == "__main__":
    n = input()
    array = [int(x) for x in input().split()]
    print(lll(array))

发表于 2021-08-05 12:08:31 回复(0)

欧皇👑是个月半球

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    bool flag=false;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int temp;
        scanf("%d",&temp);
        if(temp==i && flag==false){
            cnt++;
            flag=true;
        }else flag=false;
    }
    printf("%d",cnt);
    return 0;
}

发表于 2019-12-01 16:28:05 回复(0)

水水水水水水水水水水水水水

import sys

def main():

    n = int(input())
    a = [int(i) for i in input().split(' ')]
    res = 0

    for i in range(n-1):

        if int(a[i]) == i+1:
            a[i],a[i+1] = a[i+1],a[i]
            res +=1
    if a[n-1] == n:
        res +=1

    print(res)

if __name__ == "__main__":

    main()



python3 小白

发表于 2017-12-29 12:12:38 回复(0)

牛客812658号

var n=readline();
        var a=readline().split(" ").map(x=>parseInt(x,10));
        for(var flag=0,i=0;i<n-1;i++){
            if(a[i]==i+1){temp=a[i+1];a[i+1]=a[i];a[i]=temp;flag++;}
        }
        print(flag);

发表于 2017-12-26 01:43:48 回复(0)