累加出整个范围所有的数最少还需要几个数

[编程题]累加出整个范围所有的数最少还需要几个数

热度指数：833 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正数数组 $\ arr$ 和一个正数 $\ range$ ，可以选择 $\ arr$ 中的任意个数字加起来的和为 $\ sum$ 。

返回最小需要往 $\ arr$ 中添加几个数，使得 $\ sum$ 可以取到 $1 \sim range$ 范围上的每一个数。

给出的数组不保证有序！

输入描述:

第一行一个整数N, K。表示数组长度以及range
接下来一行N个整数表示数组内的元素

输出描述:

输出一个整数表示答案

示例1

输入

4 15
1 2 3 7

输出

说明

想累加得到范围上的所有的数，arr还缺14这个数，所以返回1

示例2

输入

3 14
1 5 7

输出

说明

想累加得到1~14范围上所有的数，arr还缺2和4，所以返回2。

备注:

算法知识视频讲解

Joseph1314

发表于 2020-04-28 23:21:01

如果没有arr数组，先看累加的到1-range范围上的所有数，最少需要几个数。缺少1，在有了1之后，就可以得到1-1范围上的所有数；需要添加新鲜的数字1，得到更新的[1,1] [1,1]缺少2，需要添加新鲜的数字2，得到更新后的[1,3] =[1,2,1+2]，实际的数字（1,2） [1,3]缺展开全文

犯困的小山竹在找内推

发表于 2021-08-12 18:51:21

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays; public c 展开全文