[codeforces 1393C] Pinkie Pie Eats Patty-cakes 桶排序+数字的两种分配形式

Codeforces Round #662 (Div. 2)   参与排名人数13194

[codeforces 1393C]   Pinkie Pie Eats Patty-cakes   桶排序+数字的两种分配形式

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1393/problem/C

题目大意：给出一堆数字，编程者可合理安排数字位置，要求雷同数字之间包含的最少数量的数字数量尽可能的大，输出这个最大的最小值。题目进一步理解如下：

7
1 7 1 6 4 4 63构造数字序列如下
1 4 6 7 1 4 61 (4 6 7) 1 4 6 雷同数字1之间有3个数字(4 6 7)
1 4 (6 7 1) 4 6 雷同数字4之间有3个数字(6 7 1)
1 4 6 (7 1 4) 6 雷同数字4之间有3个数字(7 1 4)雷同数字之间做少包含数字是3,最大最小间距是3

基本思路：相见样例模拟过程（建议结合AC代码一起阅读）。

样例模拟过程如下

7
1 7 1 6 4 4 631有2个,2有2个,6有2个,   分配形式二
7有1个   分配形式一安置过程如下：
(1)(1)
(1)(1)
(1 2)(1 2)
(1 2 6)(1 2 6)
(1 2 6 7)(1 2 6)8
1 1 4 6 4 6 4 724有3个,   分配形式二
1有2个,6有2个,   分配形式一
7有1个   分配形式一安置过程如下：
(4)(4)(4)
(4 1)(4 1)(4)
(4 1 2)(4 1 2)(4)
(4 1 2 7)(4 1 2)(4)3
3 3 303有3个,   分配形式二安置过程如下：
(3)(3)(3)6
2 5 2 3 1 44
2有2个,   分配形式二
1有1个,3有1个,4有1个,5有1个   分配形式一安置过程如下：
(2)(2)
(2 1)(2)
(2 1 3)(2)
(2 1 3 4)(2)
(2 1 3 4 5)(2)

AC代码如下：

#include <stdio.h>
#define maxn 100010
int cnt[maxn],tot;
int main(){int t,n,i,a,c,ans;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++)cnt[i]=0;for(i=1;i<=n;i++)scanf("%d",&a),cnt[a]++;c=0,tot;for(i=1;i<=n;i++)if(c<cnt[i])c=cnt[i],tot=1;else if(c==cnt[i])tot++;ans=(n-tot*c)/(c-1)+tot-1;//(n-tot*c)/(c-1)分配形式一，tot-1分配形式二printf("%d\n",ans);}return 0;
}