牛客周赛122 Digital Deletion
https://ac.nowcoder.com/acm/contest/125083/D
题目分析：
通过了解题意，我们会想到，就是求出一个集合的所有子集合的和，放入到一个新的集合里面，然后求最多删除多少个数，不会影响整体的 MEX
MEX的介绍：
mex指的是集合中未出现的最小 非负整数，举个例子{ 1 3 5 7}，那这个MEX就是2了
ok，我们最开始会想到就常规思路，先求出所有的子集合的和，然后其去求这个MEX
MEX的求法：
我们知道了mex的 定义，不难想到，为了方便，我们可以先把新的集合进行排序，从小到大，一般排序不影响做题的话，我们还是先排序一下，我们可以清晰的发现排完序的好处，比如{1 3 5 6 8 }这个新集合来说，我们如何找到MEX并且删除多余的元素，很明显，知道a[i]后，倘若a[i]+1<a[i+1]的话，此时后面的值便可以全部删掉了
但此题的关键是，我们不能全部的求出所有的字集合，因为我们会发现还真表示不出来，直接枚举是不可能的
正确的解法：
“排序+求前缀和”：高效处理所有的 子序列和的生成情况
他虽然不能完整的求出所有的子序列和的完整集合，但能精准的告诉你从0开始的连续一段区间，哪些数字一定能被生成
也就是我们要对最开始的集合先进行排序，举个例子{1 5 7 3 9}，排完序是{1 3 5 7 9}
我们求前缀和 刚开始是1，后面是4，
我们上面说的意思是，我们虽然求不出完整的子序列和，但我们求的前缀和，比如上面的4，他是保证前面1 2 3是存在，显而易见，是连续的，那么这样的话，如果要求MEX的话，我们是不是就能判断出来，如果前缀和（我用sum表示）sum+1<a[i+1]的话，是不是就可以把后面的值全部删掉就可以了，也就求出我们想要的结果了
我们可能到这里就不能理解为什么上面的 就是正确的，接下来我就给说一下自己的理解 ，但也不一定对，可能还是理解不懂，这个大家也可以找找ai问问
为什么正确？
假设我们这个集合是{1 3 5 7 9}和上面一样（记住前提是排好序的），那么我们的子序列有哪些呢？单个的，两个的相加，三个的相加，四个的相加，五个的相加
那么我们排完序后，开始求前缀和的话，也是和上面的步骤一样，但我们排完序后的元素是从小到大的，所以在执行上面的步骤时，我们的所有数都是要比上面的小的 ，我们要知道，最后得到的 新集合，他也是要排序的，从小到大，而按照我们的 方法，他每一步都会是最小的，因为我们排序了，从小到大，所以不管是单个的还是几个的相加，它都是最小的，这个大家应该可以理解明白
所以我们能证明在算法的每一步，我们能保证小于sum的所有非负整数是都能够生成的，所以如果我们的sum+1<a[i+1]的话，则说明a[i+1]确实无法被所有的子序列和生成的
继续，我们此前加入的k个数，（从头到尾），能生成的就是（0，sum），如果我们在加的话，按道理就是（0+k,sum+k）但我们的sum+k>sum+1,也就不满足题意了，就是可以把后面的全部删掉了，所以根据这个数学归纳法，我们可以假设我们最开始集合就一个数，然后一个一个的往里面加，（当然是从小到大，我们是把已有的集合从小到大排列，然后一个一个加进去的）
所以也就验证了我们这样做的正确性
小结：
如果大家不想纠结于为什么这个算法是正确的，大家只需要明白我上面写正确的解法中红字的部分即可
初步代码：
这段代码其实还是有问题的，也就是我们少判断了特例，也就是集合中出现0的情况
这里我们要明白一个问题，0这个元素，是必须能和删掉的，所以我们在a[i]时，我们要先判断输入0的次数，用一个变量统计一下
也就是最后进入到a[]里面的 ，一定是全部都是正数的才可以，最后算个数的时候再把0的个数给加上就可以了
大家可以想一下，我例举下情况{0 0 0 1 3 }，这个MEX是2，如果删了0，不影响，{0 0 0 3 5 6}，这种情况MEX是4，删了0也不影响
但如果我们把0放在我们的集合里面，我们可能会提前终止我们的结果，最后让结果偏小，这个大家应该可以理解
所以这个改动其实挺简单的 ，就是判断下这个0的个数，把0给单独拿出来就行，最后让a[]里面的全是正数即可
正确的代码：
这道题到这里就结束了，有点难度，大家多练多想，也真的欢迎有更多想法可以交流交流