首页 > 试题广场 >

小红的孤独数

[编程题]小红的孤独数
  • 热度指数：375 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一个数组，她每次可以选择一个数使其加k。小红希望数组中的每个数都和其它元素不同，她想知道最小的操作次数是多少？

输入描述:
第一行输入两个正整数n和k，用空格隔开。
第二行输入n个正整数a_i，用空格隔开。
1\leq n,k,a_i \leq 10^5


输出描述:
一个整数，代表最小的操作次数。
示例1

输入

5 2
2 3 1 3 4

输出

1

说明

选择第二个数，使得其加2，数组变成[2,5,1,3,4]，不存在两个相同的元素。
算法知识视频讲解
添加回答
Java
__what__头像 __what__
import java.util.*;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.HashMap;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Long n = in.nextLong();
        Long k = in.nextLong();
        Map<Long, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Long a = in.nextLong();
            map.put(a, map.getOrDefault(a, 0) + 1);
        }
        Set<Long> add = new HashSet<>();
        Long res = 0L;
        for(Map.Entry<Long,Integer> entries:map.entrySet()){
            Long key = entries.getKey();
            int value = entries.getValue();
            while(value > 1){
                Long temp = key+(value-1) * k;
                res += value - 1;
                while(map.containsKey(temp)){
                    res++;
                    temp += k;
                }
                while(add.contains(temp)){
                    res++;
                    temp += k;
                }
                add.add(temp);
                value--;
            }
        }
        System.out.print(res);
    }
}

//笨办法
发表于 2023-03-15 11:31:20 回复(0)
提交观点

问题信息

来自：22年秋招蚂蚁编程题精选
难度：
1条回答 1909浏览

热门推荐

通过挑战的用户

相关试题

小红的孤独数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号