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