ACGO欢乐赛#42题解

Solution

考虑每次选没出现过的数做一次排序，贡献为个数之和减一（头不用）。
可以用一个桶进行映射，这个数用完了就删掉，可以用 map 实现。

Code

#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 988444333
#define MOD 1000000007
#define in(x,y,z) x>=y&&x<=z
using namespace std;
const int N = 2e6 + 5;
int a [N];
inline int read ()
{
	int x = 0;
	bool f = 1;
	char c = getchar ();
	while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
	return (f ? x : -x);
}
inline void write (int x)
{
	if (x < 0) putchar ('-'),x = -x;
	if (x > 9) write (x / 10);
	putchar (x % 10 + '0');
	return ;
}
signed main ()
{
	int n;
	cin >> n;
	map <int,int> mp;
	for (int i = 1;i <= n;i ++)
	{
		int x;
		cin >> x;
		mp [x] ++;
	}
	int ans = 0;
	while (! mp.empty ())
	{
		vector <int> v;
		vector <int> q;
		for (auto &i : mp)
		{
//			cout << i.first << ' ' << i.second << endl;
			v.push_back (i.first);
			i.second --;
			if (i.second == 0) q.push_back (i.first);
		}
		for (int &i : q) mp.erase (i);
		ans += v.size () - 1;
	}
	cout << ans;
	return 0;
}