Make It Permutation

Make It Permutation

题意

给一个正整数数组，大小不超过。
有两种操作：删除任意一个数字，代价为；添加任意一个正整数，代价为。
通过任意次操作，让数组最终变成一个排列，求最小代价。

思路

对于暴力算法来说，枚举这个排列的长度，然后遍历一遍数组，计算代价，最后取最小值。

考虑优化：
排列一定是从开始的，所以考虑将这个数组从小到大排个序。而枚举排列的长度也可以通过线性的方式进行计算代价。

例如遍历数组，当前下标为，以为排列的长度，因为到已经遍历过了，所以我们知道有多少个不重复的元素属于到，记为。

至于没有出现的元素我们应该补上去，即个。剩下的元素全都可以删掉，于是要删掉个。

时间复杂度。

代码

void solve() {
    int n, c, d;
    std::cin >> n >> c >> d;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    int val = 0;
    i64 res = 1ll * n * c + d, num1 = 0;
    for (int i = 0; i < n; i++) {
        if(a[i] > val) {
            num1 += 1;
            val = a[i];
        }
        res = std::min(res, 1ll * c * (n - num1) + 1ll * d * (a[i] - num1));
    }

    std::cout << res << '\n';
}