2026-10-11 秋招XX笔试复盘：相同元素的间隔重排
题目：重排数组，让相同元素保持距离
题目大意
重排数组，使相同元素的下标差至少为 ，无法构造输出 -1。下面按 讨论。
这里的“间隔 ”是下标差至少为 ，中间至少隔 个元素，也就是任意连续 个元素互不相同。比如 ，数组 1 1 1 2 2 3 3 可以排成 1 2 3 1 2 3 1。
我当时的想法
我先统计频次，把不同数字按剩余次数排序，每轮取前 种。用完以后减少频次，再视情况排序。
我还做了两个优化：次数归零的数字退出后续排序；每轮只比较第 和第 个元素，只有这里出现逆序时才重新排。在完整取出 种数的一轮中，前 个计数同时减一，内部顺序不会变，后面元素的顺序也没变，新的逆序只能出现在两部分的边界。比较第 项还要先保证剩余种类数大于 。
这能少排一些次，但最坏情况仍要反复全量排序。例如 、，有100000种数、每种出现两次。前近50000轮会触发排序，却没有一种数字被彻底用完。
思路分析
统计每个数字的剩余次数，用大根堆存当前可以使用的数字。每次优先放剩余次数最多的那一种，避免高频数字拖到后面挤不下。
一个数字在位置 用过以后，下一次最早只能放在 。把它的剩余次数和解禁位置放进冷却队列，到位置了再放回堆里。由于每次解禁位置都是当前下标加固定的 ，队列本身就是按解禁时间排序的，不需要再用一个堆。
每放一个数，就严格执行“解禁、选数、重新冷却”这三个步骤。如果还没填完，堆却空了，说明剩余数字都不能放在当前位置，返回无法构造。
这个写法把距离条件直接落实到位置，不需要反复对全部不同数字排序，也不用预先猜可行性。每个元素对应一次出堆和至多一次入堆，设不同数字有 种，时间复杂度 。堆和冷却队列共用 空间，保存输出另外需要 。
参考代码
构造失败时输出 -1，成功时输出 ans；不要求字典序最小或最大。
#include <bits/stdc++.h>
using namespace std;
// 相同数的下标差至少为 k，k >= 1。
// 成功时返回 true 并写入 ans，失败返回 false。
bool rearrange(const vector<int>& a, int k, vector<int>& ans) {
ans.clear();
if (k <= 1) {
ans = a;
return true;
}
map<int, int> freq;
for (int x : a) ++freq[x];
priority_queue<pair<int, int>> available; // 剩余次数、数值
for (auto [x, count] : freq)
available.push({count, x});
// 解禁位置、剩余次数、数值，解禁位置按入队顺序递增。
queue<tuple<long long, int, int>> cooling;
ans.reserve(a.size());
for (long long pos = 0; pos < (long long)a.size(); ++pos) {
while (!cooling.empty() && get<0>(cooling.front()) <= pos) {
auto [ready, count, x] = cooling.front();
cooling.pop();
available.push({count, x});
}
if (available.empty()) return false;
auto [count, x] = available.top();
available.pop();
ans.push_back(x);
if (--count > 0)
cooling.push({pos + k, count, x});
}
return true;
}