一、问题描述
给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
返回追加到 nums 中的 k 个整数之和。
题目链接：向数组中追加 K 个整数
二、题目要求
样例
输入：nums= [1,4,25,10,25], k=2输出：5解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是2和3。nums最终元素和为1+4+25+10+25+2+3=70，这是所有情况中的最小值。所以追加到数组中的两个整数之和是2+3=5，所以返回5。
考察
动态模拟 建议用时20~40min
三、问题分析
一开始我是什么思路呢，就以样例为例，我先把样例从小到大排序：
1 4 10 25 25
要求追加最小的数字，我就从一开始判断假如第一个数字为5，那么前面插入的优先顺序可以为1 2 3 4。样例的第一个数字是1，那我们就看1~ 4中间插入，还不满足 4~10中间插入......
到了最后如果还不满足，只能选取25之后的数字插入，直到满足条件，这个方法我觉得还是比较巧妙的，但提交超时了。
于是开启漫长的优化之路，思想还是上面的思想，但其实插入的数字和直接换成等差数列求和就优化成功了。
比如1~4中间有23两个数字，k=10，需要23，k=84~10中间有56789四个数字，需要56789，k=310~25中间有14个数字，但只需要111213这三个,k=0，退出
四、编码实现
classSolution { public: longlongminimalKSum(vector<int>&nums, intk) { longlonginti,ans=0,sum=0,n=nums.size(),count,start,end;//初始化sort(nums.begin(),nums.end());//从小到大排序if(nums[i]>1)//第一个数字 { start=1,end=nums[i]-1;//首位1,末位count=end-start+1;//中间数字的个数if(count>=k)//比需求的k还多 { sum+=(start+start+k-1)*k/2;//只需要k个returnsum; } elsesum+=(start+end)*count/2;//比需求的少，全部都要k-=count; } for(i=0;i<n-1;i++)//中间部分，两两组合 { if(k==0)//退出循环条件 { returnsum; } if(nums[i+1]>nums[i])//中间有空 { start=nums[i]+1,end=nums[i+1]-1; count=end-start+1; if(count>=k) { sum+=(start+start+k-1)*k/2;//只需要k个returnsum; } elsesum+=(start+end)*count/2;//比需求的少，全部都要k-=count; } } start=nums[n-1]+1;//最后一个数字sum+=(start+start+k-1)*k/2;//向后拓展returnsum;//返回结果 } };
