题意
给出 (n) 个数字，每个数字都大于等于 1，小于等于 n。现在问怎么排列使得任意两个相同的数字之间的最小距离最大。
思路
看完就直接想到了二分，二分最小距离。
关键就在check函数怎么写？
首先按照出现次数从大到小排序，优先处理出现次数多的。
依次遍历数字，对于当前数字，找到第一个可以放的位置，然后该位置 +=x（x是当前检验的最小距离），即接下来这个数字可以放的位置，如果新得到的位置已经有数字，那么向后遍历找到第一个没有数字的位置。
如果该数字没有放完，并且此时可以放的下标已经超过 n 了，那么当前距离就不合法。
但是 WA 了。
比如这个样例：
1
10
1 1 2 2 3 3 4 4 4 4
在检验 x 为 2 的时候，会形成下面的排列：
4 1 4 1 4 2 4 2 3 3
这是不合法的。最后会输出0。
但是可以这样排列：4 3 2 4 3 1 4 2 1 4，答案应该是2。
然后二分我想不到怎么放了。
看着样例突然想到了模拟：
我们按照最大的出现次数分组，每组最初都有一个最大出现次数的数字。
比如上面的样例，有4 个 4，那么我们分成 4 组，。
①：4
②：4
③：4
④：4
接下来我们按照出现次数从高到低的数字往每个组里放数字：1 2 3。
①：4，1，2
②：4，1，3
③：4，2，3
④：4
答案就是 2。
这里产生一个问题，也就是最后一组到底要不要放数字？
乍一看不放数字是最好的，但是会出问题，比如：
2 2 2 1 1 1 3 3 3
如果不放会变成如下这样：
①：1，2，2，3
②：1，2，3，3
③：1，
这样排列相同的就直接在一起了。
原因就是有多个出现次数相同的，那么可以这样放：如果该数字的出现次数和最大次数相同，那么最后一组就应该放，否则最后一组不放。
此时答案为长度最短的一个组的长度 - 1。
代码
/*
* @Autor: valk
* @Date: 2020-04-04 14:56:12
* @LastEditTime: 2020-09-16 19:47:11
* @Description: 如果邪恶 是华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
*/
#include <bits/stdc++.h>
#define fuck system("pause")
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int arr[N], cnt[N];
int main()
{
int _;
scanf("%d", &_);
while (_--) {
memset(cnt, 0, sizeof(cnt));
int n;
scanf("%d", &n);
int maxn = -1, num = -1;
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
cnt[arr[i]]++;
maxn = max(maxn, cnt[arr[i]]);
}
int rel = n;
for (int i = 1; i <= n; i++) {
if (cnt[arr[i]] == maxn) {
rel--;
}
}
sort(arr + 1, arr + 1 + n);
n = unique(arr + 1, arr + 1 + n) - arr - 1;
for (int i = 1; i <= n; i++) {
if (cnt[arr[i]] == maxn) {
num++;
}
}
printf("%d
", num + rel / (maxn - 1));
}
return 0;
}
/*
1
10
1 1 2 2 3 3 4 4 4 4
4
7
1 7 1 6 4 4 6
*/