4306. 序列处理

一.题目

给定一个长度为 n 的整数序列 a1,a2,…,an。

我们可以对该序列进行修改操作，每次操作选中其中一个元素，并使其增加 1。

现在，请你计算要使得序列中的元素各不相同，至少需要进行多少次操作。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示所需的最少操作次数。

数据范围

前 66 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤3000，1≤ai≤n。

输入样例1：

1
2
4
1 3 1 4

输出样例1：

1
1

输入样例2：

1
2
5
1 2 3 2 5

输出样例2：

1
2

二.笔者见解

本题属于acwing的中等难度题目，解题难点在于思路不好理清，当理清思路后会发现次题的破解难度不大。

在这里作者建议，灵活使用两个一维数组，一个数组用来存数值，用另一个数组的下标用来帮助数值变化。

三.解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        //记录这N个数值数值
        int[] arr = new int[n];int res = 0;
        int[] num = new int[100000];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        //排序
        Arrays.sort(arr);

        for (int i = 0; i < n; i++) {
            while(num[arr[i]] != 0){arr[i]++;res++;}
            num[arr[i]]++;
        }
        System.out.println(res);


    }
}