题目描述
胖头鱼在苦恼“沉鱼落雁”是什么好吃的东西，这很显然是因为他成语没背够。
于是他决定开始背成语。胖头鱼身为鱼界大佬，背成语的姿势自然也和常人不一：
他会先将所有要背的成语一字排开，比较难背的成语会重复出现，最多重复 3 次 (也就是出现次数可能为 1, 2 或 3)。这样就得到了一个可能有重复元素的成语序列，然后他会将这个序列打乱顺序，并按打乱后的顺序背下去。为了均匀的背所有成语，提高背成语的效率，相同成语在打乱后的序列中出现位置的最小间隔自然是越大越好。 (编号为 a 和 b (a<b) 的两个位置的间隔定义为 b?a?1)
现在胖头鱼把打乱前的成语序列给你，你需要帮他打乱顺序，使得相同成语的最小间隔最大。
你不需要输出确切的方案，仅求出最小间隔的最大值即可。
特别地，当每种成语都只出现一次时，把最小间隔的最大值视为n。
输入描述
第一行一个整数 n ( 1≤n≤10^5)，表示成语序列长度为 n。同一个成语最在序列中最多出现 3 次。
接下来 n 个整数 a1, a2, …, an (1≤ai≤10^9) 表示一个成语序列，每个正整数都代表一个成语，两个成语不同当且仅当值不同。
输出描述
输出一个整数，表示最小间隔的最大值。
样例输入 1
9
5 4 3 1 3 1 1 5 5
样例输出 1
2
样例解释1
其中一組可行方案是1 3 5 1 3 5 1 4 5，容易验证没有比 22 更大的答案。
样例输入2
5
1 2 3 4 5
样例输出2
5
链接：
https://www.cometoj.com/contest/65/problem/B?problem_id=3683
解析：
思维题。
我们可以统计出现三次两次一次元素的个数，分别记为a,b,c;
假设11122233344556，我们可以发现有3个出现三次元素，2个出现两次的元素，1个出现一次的元素。我们可以这样 123 45 6 123 45 6 123这样分。
那么这时间隔为a-1+b+c/2，下取整。
如果没有出现三次的元素，例如112234
我们可以 12 3 4 12这样分
即 a+b-1
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+20;
int a[maxn];
map<int, int> mp;
int main()
{
ios::sync_with_stdio(false);int n;cin >> n;mp.clear();int count1,count2,count3;count1 = count2 = count3 = 0;for(int i = 0; i < n; i++) {
cin >> a[i];mp[a[i]]++;}int mx = 0;for(auto u:mp) {
if(u.second == 1)count3++;else if(u.second == 2)count2++;else if(u.second == 3)count1++;mx = max(mx, u.second);}if(mx == 1) {
cout << n << endl;}else if(mx == 2){
cout << count2 + count3 - 1 << endl;}else cout << count1 + count2 - 1 + (count3/2) << endl;return 0;
}