Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

I give you an integer array nums and an integer k. Append k distinct positive integers that do not appear in NUMS to numS and minimize the sum of the elements in the result array.

Returns the sum of k integers appended to nums.

Append K integers to array.

Two, the title requirements

The sample

Input: nums = [1,4,25,10,25], k = 2 output: 5 The sum of the final nums elements is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum in all cases. So the sum of the two integers appended to the array is 2 + 3 = 5, so return 5.Copy the code

inspection

1. Dynamic simulation 2. The recommended time is 20 to 40 minutesCopy the code

Third, problem analysis

What was my initial thought? Let’s take examples. I’ll order them from smallest to largest:

1, 4, 10, 25, 25Copy the code

To append the smallest number, I decided from the beginning that if the first number was 5, the order of precedence could be 1, 2, 3, and 4. If the first digit of the sample is 1, then we can see the intermediate insertion from 1 to 4, but not from 4 to 10……

At the end of the day, if you still don’t meet the requirement, you can only choose the number after 25 and insert it until the condition is satisfied. I think this method is quite clever, but the submission times out.

So the long way down the optimization road, the idea is the same as above, but in fact, the sum of the inserted numbers is directly replaced by the arithmetic sequence of the optimization is successful.

For example, if there are 2 and 3 digits between 1 and 4,k= 10 requires 2, 3, and K =8. If there are 5, 6, 7, 8, 9 digits between 4 and 10, 5, 6, 7, 8, 9, and k=3, there are 14 digits between 10 and 25, but only 11, 12, 13 are needed. K =0 and exitCopy the code

Four, coding implementation

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        long long int i,ans=0,sum=0,n=nums.size(),count,start,end;/ / initialization
        sort(nums.begin(),nums.end());// Sort from smallest to largest
        if(nums[i]>1)// The first number
        {
            start=1,end=nums[i]- 1;// The first digit is 1 and the last digit is 1
            count=end-start+1;// The number of middle digits
            if(count>=k)// More than k is required
            {
                sum+=(start+start+k- 1)*k/2;// Only k
                return sum;
            }
            else
                sum+=(start+end)*count/2;// Less than required, all of them
            k-=count;
        } 
        for(i=0; i<n- 1; i++)// The middle part, in pairs
        {
            if(k==0)// Exit the loop condition
            {
                return sum;
            }
            if(nums[i+1]>nums[i])// The middle is free
            {
                start=nums[i]+1,end=nums[i+1]- 1;
                count=end-start+1;
                if(count>=k)
                {
                    sum+=(start+start+k- 1)*k/2;// Only k
                    return sum;
                }
                else
                    sum+=(start+end)*count/2;// Less than required, all of them
                k-=count;
             }  
        }
        start=nums[n- 1] +1;// The last number
        sum+=(start+start+k- 1)*k/2;// Extend backwards
        return sum;// Return the result}};Copy the code

V. Test results