lc周赛里抄的题目

https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/

将数组排序后枚举，若前一个数是l,后一个数是r，则需要添加r-l+1个数，和增加 (l+1)+...+(r-1)（这个值用等差数列公式算。）

时间复杂度主要体现在排序上，是\(\mathcal{O(n \log n)}\)

最终输出ans。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;cin>>n>>k;
    vector<long long> a(n+2, 0); for(int i=1;i<=n;i++) cin>>a[i];
    a[0] = 0;
    a[n+1] = 1e10;
    sort(a.begin(), a.end());
    long long ans = -1e10;
    for(int i=1;i<=n+1;i++)
    {
        ans+=a[i];
        int t = a[i] - a[i-1] - 1;
        if(t >= 0)
        {
            if(k>=t)
            {
                k-=t;
                ans += (a[i]-1 + a[i-1]+1) * (a[i]-1 - a[i-1]) / 2;
            }
            else
            {
                ans += (a[i-1]+1 + a[i-1]+k) * k / 2;
                k=0;
            }
        }
    }
    cout<<ans;
    return 0;
}