题目链接

解题思路

我们将整个数组看成
aaaaaaaaa bbbbcccddddeeff....
其中a为出现次数最多的数字。
然后将数字插入每一个a的空档中。
可以保证一定有插法不会在不是出现次数最大的数字中间出现距离最短。
于是我们最优插法就是将其均摊到每一个空档中间。
于是得出公式

$$ ans=(n-maxsum*Max)/(Max-1)+maxsum-1 $$

代码

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[100005];
int main(){
    cin>>T;
    for(int cas=1;cas<=T;cas++){
        cin>>n;
        int Max=0,maxsum=0;
        int tmp;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++){
            cin>>tmp;
            a[tmp]++;
            if(a[tmp]>Max){
                Max=a[tmp],maxsum=1;
            }else if(a[tmp]==Max){
                maxsum++;
            }
        }
        cout<<(n-maxsum*Max)/(Max-1)+maxsum-1<<endl;
    }
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/676/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者