题意大概是给我们一串数，问我们任意排列中相邻两个相同数的最小距离。
因为是CF的C题，而且这题面看完之后感觉就很贪心，所以我们开始构造一种贪心方案。
不难发现，要让相同数之间的距离更大，显然要把出现次数多的数往里面塞。
那么我们二分一下答案，对于每一次判断，我们使用优先队列维护一下，每次放进去出现次数最多的k个即可。
下附代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 int cnt[100005],res[100005],c[100005],n; 7 priority_queue<pair<int,int> > q; 8 struct node{ 9 int t,num; 10 }a[100005]; 11 bool cmp(node x,node y){ 12 return x.t>y.t; 13 } 14 bool judge(int x){ 15 for (int i=1; i<=n; i++) c[i]=cnt[i]; 16 for (int i=1; i<=n; i++){ 17 if (cnt[i]!=0){ 18 q.push({cnt[i],i}); 19 } 20 } 21 for (int i=1; i<=n; i++){ 22 if (i-x-1>=1 && c[res[i-x-1]]) q.push({c[res[i-x-1]],res[i-x-1]}); 23 if (q.empty()) return 0; 24 res[i]=q.top().second,c[res[i]]--,q.pop(); 25 } 26 return 1; 27 } 28 int erfen(){ 29 int l=0,r=n; 30 while(l<r){ 31 int mid=(l+r+1)>>1; 32 if (judge(mid)) l=mid; 33 else r=mid-1; 34 } 35 return l; 36 } 37 int main(){ 38 int T; 39 scanf("%d",&T); 40 while (T--){ 41 scanf("%d",&n); 42 for (int i=1; i<=n; i++) cnt[i]=0; 43 for (int i=1; i<=n; i++){ 44 int x; 45 scanf("%d",&x); 46 cnt[x]++; 47 } 48 printf("%d ",erfen()); 49 } 50 return 0; 51 }