CodeTON Round 4 (Div. 1 + Div. 2)C

更好的阅读体验

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("%lldn", val + ans);
}
 
int main()
{
//	freopen("1.in", "r", stdin);
	int t;cin >> t;
	while(t --)	run();	
	return 0;  
}