题目描述
给定一个长度为l的有序非负整数列nums和一个整数n，最少需要添加多少个数可以使得[1,n]间的每一个数都可以被数列中若干个数的和来表示。(数组中的元素不能重复使用)
输出最少需要添加多少个数字。
输入格式 共计两行。 第一行：两个整数l和n，分别代表数列nums的长度和整数n。(l不大于10^5，n不大于INT_MAX)
第二行：l个有序非负整数。(每个数不大于10^4)
输出格式 最少需要添加的数字个数
样例
样例1输入 2 6 1 3 样例1输出 1
样例2输入 3 20 1 5 10 样例2输出 2
算法分析
本题要采用贪心算法，让使用的补丁最少，且能覆盖范围内的所有值，达到最简的。
代码
#include
<cstdio
>
#include
<algorithm
>
using namespace std
;
const int M
= 10000005;
int a
[M
];
int
main() {
int n
, m
;
scanf("%d %d", &n
, &m
);
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &a
[i
]);
}
int sum
= 0, ans
= 0;
for (int i
= 1; i
<= n
;) {
if (sum
>= m
) {
break;
} else if (sum
+ 1 < a
[i
]) {
ans
++;
sum
+= sum
+ 1;
} else {
sum
+= a
[i
];
i
++;
}
}
while (sum
< m
) {
ans
++;
sum
+= sum
+ 1;
}
printf("%d", ans
);
}
