C. Make It Permutation

我们希望尽可能少地进行操作可以使代价最小,我们如果要排列的话,那些重复的元素我们无论如何都要进行删除的,所以我们可以先把去重的代价计算出来,然后依次枚举排列的位数是多少,也就是枚举去重后的数组,其中的代价我们可以一次计算出来,当我们枚举第i个a时,前面1有 i - 1个数,而1~ai - 1所有数都需要有,所以一共需要补ai - i个数,而i后面所有数都需要删除需要删m - i个数,代价我们可以通过O(1)的时间复杂度计算出来,然后枚举i更新答案即可。

时间复杂度:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int c[N];

void run()
{
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
LL val = 0, ans = 2e18;
set<int>s;
for(int i = 0; i < n; ++ i)
{
int x; scanf("%d", &x);
if(s.find(x) == s.end()) s.insert(x);
else val += a;
}
int m = 0;
for(auto it : s) c[++ m] = it;

for(int i = 1; i <= m; ++ i)
{
LL k = 1LL * (c[i] - i) * b + 1LL * (m - i) * a;
ans = min(k, ans);
}
ans = min(ans, 1LL * m * a + b);
printf("%lld\n", val + ans);
}

int main()
{
// freopen("1.in", "r", stdin);
int t;cin >> t;
while(t --) run();
return 0;
}