更好的阅读体验

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;  
}