您现在的位置是：首页 >技术教程 >【贪心】个人练习-Leetcode-2195. Append K Integers With Minimal Sum网站首页技术教程

题目链接：https://leetcode.cn/problems/append-k-integers-with-minimal-sum/

题目大意：给出一个数组nums[]，现在要往里面追加k个【互不相同】且【未出现在nums[]中】的【正整数】，使得这k个数字之和最小。

思路：明显就是贪心，从1开始塞进去即可。但是单纯的【累加+用set判断是否在nums[]中会超时】，毕竟当k很大以及冲突很多时太慢了。不如用【等差数列的和】公式来做。

先将nums[]排序，然后规定当前可加入的数字的区间上下限left, right，left从1开始。计算区间长度len，如果加上len还不够k个，那么全加上（利用等差数列求和公式）；否则只加上k-cnt个，并且立即返回。

当然，如果出现【nums[]中连续两个数字相同】的情况，当前区间的长度len会变成非正数，此时要跳过。

nums[]中元素如果遍历完了还没有满足k个，那么继续加到满足为止。

完整代码：

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int N = nums.size();

        long long ret = 0;
        int cnt = 0;
        long long left = 1, right;

        for (int i = 0; i < N; i++) {
            right = nums[i] - 1;
            int len = right - left + 1;
            if (len <= 0) {
                left = nums[i] + 1;
                continue;
            }

            if (cnt + len <= k) {
                ret += (left + right) * len / 2;
                cnt += len;
            }
            else {
                int need = k - cnt;
                ret += (left + left + need - 1) * need / 2;
                cnt += need;
            }

            if (cnt == k)
                return ret;
            else 
                left = nums[i] + 1;
        }

        if (cnt < k) {
            int need = k - cnt;
            ret += (left + left + need - 1) * need / 2;
        }

        return ret;
    }
};