SCU每日一题
FallenGemini

Make It Permutation

Make It Permutation

题意

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

思路

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

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

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

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

时间复杂度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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';
}