欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法题——正则序列

程序员文章站 2024-03-22 18:17:04
...

我们称一个长度为n的序列为正则序列,当且仅当该序列是一个由1~n组成的排列,即该序列由n个正整数组成,取值在[1,n]范围,且不存在重复的数,同时正则序列不要求排序

有一天小团得到了一个长度为n的任意序列,他需要在有限次操作内,将这个序列变成一个正则序列,每次操作他可以任选序列中的一个数字,并将该数字加一或者减一。

请问他最少用多少次操作可以把这个序列变成正则序列?

输入描述:
输入第一行仅包含一个正整数n,表示任意序列的长度。(1<=n<=20000)

输入第二行包含n个整数,表示给出的序列,每个数的绝对值都小于10000。

输出描述:
输出仅包含一个整数,表示最少的操作数量。

输入例子1:
5
-1 2 3 10 100

输出例子1:
103

public class Test02{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n;
        n=scanner.nextInt();
        scanner.nextLine();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        //对数组a排序
        Arrays.sort(a);
        int count=0;
        for(int i=1;i<=n;i++){
            //(贪心)每一个数字最短距离是升序后的a[i]到i的绝对值
            // 比如0是第一位,第一位为1,则最短距离为abs(0-1)
            // 假如不排序一步步加减 算法很复杂且很容易死循环
            count += Math.abs(a[i-1]-i);
        }
        System.out.print(count);
    }
}

相关标签: 算法 java