正则序列

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strSeq = br.readLine().trim().split(" ");
        int[] seq = new int[n];
        for(int i = 0; i < n; i++) seq[i] = Integer.parseInt(strSeq[i]);
        Arrays.sort(seq);
        int modifyTimes = 0;
        for(int i = 1; i <= n; i++) modifyTimes += Math.abs(seq[i - 1] - i);
        System.out.println(modifyTimes);
    }
}

#include<iostream>
using namespace std;

const int N = 2e4 + 5;
int n;
int a[N], tmp[N];

int main()
{
    cin >> n;
    
    int _max = 0;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        tmp[a[i] + 10000]++;
        _max = max(_max, a[i] + 10000);
    }
    
    int idx = 0;
    for (int i = 0; i <= _max; i ++ ) {
        if (!tmp[i]) {
            continue;
        }
        while (tmp[i] -- > 0) {
            a[idx ++ ] = i - 10000;
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        ans += abs(i - a[i - 1]);
    }
    
    cout << ans << endl;
    
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)
        cin >> nums[i];
    int count = 0;
    sort(nums.begin(), nums.end());
    for(int i = 0; i < n; i++)
    {
        if(nums[i] >= 1 && nums[i] <= n)
            swap(nums[i], nums[nums[i] - 1]);
    }
    for(int i = 1; i <= n; i++)
    {
        if(i != nums[i - 1])
            count += abs(nums[i - 1] - i);
    }
    cout << count << endl;
    return 0;
}

package main
import (
	"fmt"
	"sort"
)
func S(nums []int)int{
	sort.Ints(nums)
	res:=0
	n:=len(nums)
	var less,more []int
	myMap:=make(map[int]int,n)
	for i:=0;i<n;i++ {  //把随意序列存进map并记录有多少个重复
		myMap[nums[i]] += 1
	}
		for i:=1;i<=len(nums);i++{ //循环正则序列的值，与随意序列比较有无多或少元素，多存进more，少存进less

			v,ok:=myMap[i]
			if nums[i-1]<1||nums[i-1]>=n+1{ //注意把超过n范围的元素加入more
				more=append(more,nums[i-1])
			}
			if ok{
				if v>1{
					add(&more,v-1,i)
					continue
				}
				continue
			}

			less=append(less,i)
		}

	for i:=len(more)-1;i>=0;i--{ //此时more和less已经排序浩，长度相等，逐个相减累加和，就是结果
		if more[i]>less[i]{
			res+=more[i]-less[i]
		}else{
			res+=less[i]-more[i]
		}
	}
	return res
}



func add(a *[]int, b,c int){
	for i:=1;i<=b;i++{
		*a=append(*a,c)
	}
}
func main(){
	var n int
	fmt.Scan(&n)
	nums:=make([]int,n)

	for i:=0;i<n;i++{
		fmt.Scan(&nums[i])
	}
	res:=S(nums)
	fmt.Println(res)
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr1=new int[n];
        int[] arr2=new int[n];
        for (int i = 0; i < n; i++) {
            arr1[i]=i+1;
            arr2[i]=sc.nextInt();
        }
        Arrays.sort(arr2);
        int sum=0;
        for (int i = 0; i < n; i++) {
            arr1[i]=Math.abs(arr1[i]-arr2[i]);
            sum+=arr1[i];
        }
        System.out.println(sum);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] arr = new int[n];
        int res = 0;
        for(int i = 0;i<n;i++){
            arr[i] = s.nextInt();
        }
        Arrays.sort(arr);
        while(arr[0] < 1){
            arr[0]++;
            res++;
        }
        for(int i = 1;i<n;i++){
            while(arr[i] <= arr[i-1]){
                arr[i]++;
                res++;
            }
        }
        System.out.println(res);
    }
}

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int t = 0;
    int count = 0;
    vector<int> hash(n + 1,0);
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t >= 1 && t <= n) {
            hash[t]++;
        }
        else if (t < 1) {
            count = count + 1 - t;
            hash[1]++;
        }
        else if (t > n) {
            count = count + t - n;
            hash[n]++;
        }
 
    }
    int sum = 0;
    for(int i=1;i<=n;i++) {
        sum = sum + hash[i] * i;
    }
    count = count + (1+n)*n/2 - sum;
 
    cout << count ;
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ans = 0;
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int k = in.nextInt();
            if (k < 1) {
                ans += 1 - k;
                a[1]++;
            } else if (k > n) {
                ans += k - n;
                a[n]++;
            } else {
                a[k]++;
            }
        }
        int x = 1;
        for (int i = 0; i <= n; i++) {
            while (a[i] > 1) {
                while (a[x] != 0) x++;
                ans += Math.abs(i - x);
                a[i]--;
                a[x]++;
            }
        }
        System.out.println(ans);
    }
}

import java.util.Scanner; 
import java.lang.Math;

// 贪心算法：对序列 s 进行排序，第 i 位通过加减乘除变成 i
// 优化：采用桶排序
public class Main {
    public static void main(String[] args) {
        // value 映射到 value+10000 上
        int[] buckets = new int[20001];
        // 输入数组，放入桶中
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            ++buckets[scanner.nextInt()+10000];
        }
        // 第 i 位通过加减乘除变成 i
        int result = 0, i = 1;
        for (int j = 0; j <= 20000; ++j) {
            while (buckets[j]-- > 0) {
                result += Math.abs((j-10000) - (i++));
            }
        }
        System.out.println(result);
    }
}