思路

二分、贪心。

二段性：假设最优解是 $ans$，即每个 $order$ 中的相同数字存在一个最小间隔，所有 $order$ 的最小间隔的最大值是 $ans$。当 $x > ans$ 时，不存在某个 $order$，它的最小间隔是 $x$，否则 $ans$ 就不是最优解。当 $x \le ans$ 时，可构造出一种 $order$ 使得它的最小间隔是 $x$。特别地，取最小间隔是 $ans$ 的那个 $order$，假设最小间隔的端点是 $l, r$，则将 $r - 1$ 与 $r$ 交换，就可使序列的最小间隔变成 $ans - 1$。由归纳法，可以构造出小于等于 $ans$ 的所有最小间隔。

如何判断是否存在一种 $order$，它的最小间隔是 $d$。考虑一种特殊情况：当元素种数小于 $d + 1$ 时，如果存在同种元素，它们的间隔一定小于 $d$。反证：假设同种元素间隔大于等于 $d$，则元素种数一定大于等于 $d + 1$，因为间隔里都是不同种元素。反之，如果不存在同种元素，则任意排列都是可行解。即当元素种数小于 $d + 1$ 时，问题有解等价于不存在同种元素。

根据以上特例，应该让个数最多的元素排在前面，避免最后元素种数过少时，仍然存在相同元素。由此得出贪心策略：每次取最近 $d + 1$ 步没有用过且个数最多的个元素。证明：若存在可行解，则贪心也可行。假设解存在但贪心不可行。首先，可行解每次使用的一定也是最近 $d + 1$ 步没有用过的元素，否则最小间隔就小于 $d$。那么可行解一定先使用了不是个数最多的某些元素，这样会使个数较少的元素先用完，个数较多的元素后用完，导致元素种数较少时，每种元素的个数较多，更容易出现以上特例导致最后的元素无法排开。因此若存在可行解，则贪心也可行（有待严谨证明）。

时间复杂度$O(nlog^2n)$。

写法一

用队列维护最近 $d + 1$ 步使用过的元素，用平衡树维护维护个数最多的元素。

#include <iostream>
#include <map>
#include <unordered_map>
#include <queue>

#define endl "\n"

using namespace std;

bool ok(multimap<int, int, greater<int>> cnt, int d) {
  queue<pair<int, int>> q;
  while (cnt.size()) {
    auto it = cnt.cbegin();
    auto [x, y] = *it;
    cnt.erase(it);
    q.push({x - 1, y});
    if (q.size() > d) {
      auto [x, y] = q.front();
      if (x > 0) cnt.insert({x, y});
      q.pop();
    }
  }
  while (q.size()) {
    if (q.front().first > 0)
      return false;
    q.pop();
  }
  return true;
}

void solve() {
  int n;
  cin >> n;

  unordered_map<int, int> cnt;
  for (int i = 0, x; i < n; i++) {
    cin >> x;
    cnt[x]++;
  }

  multimap<int, int, greater<int>> tnc;
  for (auto [k, v] : cnt) tnc.insert({v, k});

  int l = 0, r = n - 2;
  while (l < r) {
    int mid = l + r + 1 >> 1;
    if (ok(tnc, mid)) l = mid;
    else r = mid - 1;
  }
  cout << l << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

写法二（不推荐）

实际上，不需要严格维护最近 $d + 1$ 步使用过的元素，当每次按照元素个数降序选择 $d + 1$ 个元素时，只需记录当前段使用过哪些元素。因为当前段如果使用了上一段元素，由于上一段元素个数之前是降序，现在还是降序，因此会按原始顺序选择，这样就保证了每个位置都不会使用最近 $d + 1$ 步使用过的元素（当前段已被记录，如果使用了上一段元素，两次间隔一定是 $d$）。

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>

#define endl "\n"

using namespace std;

bool ok(unordered_set<int> cat, multimap<int, int, greater<int>> cnt, int d) {
  while (cat.size() >= d + 1) {
    int k = d + 1;
    auto it = cnt.cbegin();
    vector<pair<int, int>> upd;
    while (k--) {
      auto [x, y] = *it;
      it = cnt.erase(it);
      if (x > 1) upd.push_back({x - 1, y});
      else cat.erase(y);
    }
    for (auto p: upd) cnt.insert(p);
  }
  return cnt.size() == cnt.count(1);
}

void solve() {
  int n;
  cin >> n;

  unordered_set<int> cat;
  unordered_map<int, int> cnt;
  for (int i = 0, x; i < n; i++) {
    cin >> x;
    cat.insert(x);
    cnt[x]++;
  }

  multimap<int, int, greater<int>> tnc;
  for (auto [k, v] : cnt) tnc.insert({v, k});

  int l = 0, r = n - 2;
  while (l < r) {
    int mid = l + r + 1 >> 1;
    if (ok(cat, tnc, mid)) l = mid;
    else r = mid - 1;
  }
  cout << l << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}