给定 $n$ 个数,要求将 $n$ 个数进行排列,使得所有数值相同的点对的距离的最小值尽量大。
答案为 $\lfloor \cfrac {n-\text{cnt}}{\text{maxfreq}}\rfloor$,其中 $\text{maxfreq}$ 为相同数值的数出现的最大频率,$\text{cnt}$ 为出现频率为 $\text{maxfreq}$ 的数值的个数。
假设出现频率为 $\text{maxfreq}$ 的数为 $a,b,c$。
考虑这样放置:$a,b,c,\ldots.a,b,c,\ldots.a,b,c,\ldots a,b,c$
接下来对剩余的数按出现频率排序后,按数字标注顺序依次放置即可: $a,b,c,1,4,7,10,a,b,c,2,5,8,11,a,b,c,3,6,9,a,b,c$