LeetCode 2195. 向数组中追加 K 个整数（贪心）

示例 1：
输入：nums = [1,4,25,10,25], k = 2
输出：5
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。

示例 2：
输入：nums = [5,6], k = 6
输出：25
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。
nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。
 
提示：
1 <= nums.length <= 10^5
1 <= nums[i], k <= 10^9

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long ans = 0;
        int prevnum = 0;
        for(int i = 0; i < nums.size() && k; ++i)
        {
            prevnum = (i > 0) ? nums[i-1] : 0;
            prevnum++;
            if(prevnum < nums[i]) // 前后两个数字之间有可取的数字
            {
                int n = min(k, nums[i]-prevnum);// 项数
                k -= n; // 更新还要取的个数
                ans += (1LL*prevnum+prevnum+n-1)*n/2; // 更新答案
            }
        }
        if(k) // 还有没有取的
        {
            prevnum = nums.back()+1;
            ans += (1LL*prevnum+prevnum+k-1)*k/2;
        }
        return ans;
    }
};