向数组中追加 K 个整数

题目

给你一个整数数组 nums 和一个整数 k 。

请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。

返回追加到 nums 中的 k 个整数之和。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum

思路

简单模拟，注意数据范围，不能简单的枚举每个元素

代码

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {


        long long sum=0;
        long long cnt=0;
        nums.push_back(0);                   // 添加0
        set<int> st(nums.begin(),nums.end());
        nums.clear();
        nums.insert(nums.end(),st.begin(),st.end());
        // 直接枚举每个元素，超时，使用等差数列
        // 考察模拟、数学

        for(int i=0;i<nums.size();i++){

            if(i+1<nums.size()){
                cnt+=nums[i+1]-nums[i]-1;
                
                sum+=(long long)(nums[i+1]+nums[i])*(nums[i+1]-nums[i]-1)/2;
                if(cnt>k){
                sum-=(long long)(nums[i+1]-1+nums[i+1]-(cnt-k))*(cnt-k)/2;
                return sum;
                }
            }
            else{
                sum+=(long long)(nums[i]+1+nums[i]+(k-cnt))*(k-cnt)/2;

                return sum;
            }
        }

        return 0;


    }
};