C. Pinkie Pie Eats Patty-cakes(二分)

Problem - C - Codeforces

小粉饼买了一袋不同馅料的馅饼饼!但并不是所有的馅饼饼在馅料上都各不相同。换句话说，这个袋子里有一些馅料相同的馅饼。小粉派一个接一个地吃蛋糕。她喜欢玩，所以她决定不只是吃馅饼蛋糕，而是尽量不经常吃同样馅料的馅饼蛋糕。为了做到这一点，她希望吃到的馅料与吃到的馅料之间的最小距离尽可能大。在这里，小手指把两块馅饼之间的距离严格地称为它们之间吃的馅饼的数量。小粉派可以按任何顺序吃馅饼蛋糕。她没有耐心吃完所有的馅饼蛋糕，所以她让你帮她数一下在所有可能的吃顺序中，吃完的馅饼蛋糕与相同馅料之间的最大最小距离!小粉派打算多买几袋馅饼饼，所以她让你解决这个问题，买几袋!输入第一行包含一个整数T (1 <T < 100):您需要解决问题的袋子数量。每个袋子描述的第一行包含一个整数n (2 < n≤105):里面的馅饼饼的数量。袋子描述的第二行包含n个整数a1, a2，， an (1 < a S n): patty-cakes的馅料信息:相同的馅料定义为相同的整数，不同的馅料定义为不同的整数。保证每袋至少有两个馅料相同的馅饼。保证所有袋子的n个和不超过105个。输出每个袋子在单独一行打印一个整数:在该袋子所有可能的食用顺序中，食用相同馅料的馅饼饼之间的最大最小距离。

Example

input

Copy

4
7
1 7 1 6 4 4 6
8
1 1 4 6 4 6 4 7
3
3 3 3
6
2 5 2 3 1 4

output

Copy

3
2
0
4

 请注意对于第一个袋子，Pinkie Pie可以按照以下顺序(按馅料)吃馅饼蛋糕:1,6,4,7,1,6,4(这样，最小距离等于3)。对于第二个袋子，Pinkie Pie可以按照以下顺序(按馅料)吃馅饼蛋糕:1,4,6,7,4,1,6,4(这样，最小距离等于2)。

题解:

看到最大最小就应该往二分上想了(好久没写二分了)

那如何check呢,我们check的应该是间隔为mid可不可以

举个例子：

1 1 1 1 2 2 2 2 3 4 5 6 7 8

1 2 (3 4) 1 2 (5 6) 1 2 (7 8) 2 6

1 1 1 2 2 2 3 3 3

123 123 123

看间隔为x,n - st + 1是否可以放下

st是出现数目从大往小第几个,因为前面已经放过一个大的了,肯定不能再放了,贪心来讲肯定是要先放大的

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int long long
int cnt[100050];
bool cmp(int x,int y)
{return x > y;
}
int n;
int check(int x)
{int st = 1;for(int i = 1;i <= n&&cnt[i];i++){int s = cnt[i];for(int j = st;j <= n&&s;j += (x + 1)){s--;} if(s > 0)return 0;st++;}return 1;
}
void solve()
{memset(cnt,0,sizeof cnt);cin >> n;for(int i = 1;i <= n;i ++){int x;cin >> x;cnt[x] ++;}sort(cnt + 1,cnt + 1+n,cmp);int l = 1,r = n;while(l <= r){int mid = (l + r)/2;if(check(mid)){l = mid + 1;}else{r = mid - 1; }}cout << l - 1 <<"\\n";
}signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--){solve(); }
}