Flowers（二分答案）

链接：https://ac.nowcoder.com/acm/contest/7830/J 来源：牛客网  

题目描述

Recently Jack becomes much more romantic. He would like to prepare several bunches of flowers. Each bunch of flowers must have exactly M flowers. As Jack does not want to be boring, he hopes that flowers in the same bunch are all different species. Now there are N{N}N species of flowers in the flower shop, and the number of the i-th species of flower is aia_iai​. Now Jack would like to know how many bunches of flowers he can prepare at most. (Flowers are used to propose.)\textit{(Flowers are used to propose.)}(Flowers are used to propose.)

输入描述:

The first line contains an integer T{T}T (1≤T≤101 \le T \le 101≤T≤10) --- the number of test cases. In the first line of each test case, there are two integers N{N}N, M{M}M (1≤N,M≤300 0001 \le N, M \le 300\,0001≤N,M≤300000) --- the number of flowers' species and the number of flowers in a bunch. In the second line of each test case, there are N{N}N integers --- the i{i}i-th integer indicates aia_iai​ (1≤ai≤1091 \le a_i \le 10^91≤ai​≤109), the number of i{i}i-th species' flowers.

输出描述:

For each test case, output one integer in one line --- the answer of the corresponding test case.

示例1

输入

复制1 5 3 1 1 1 2 1

1 5 3 1 1 1 2 1

输出

复制2

2

题意：

有n种花，然后要求每束花种至少有m种不同种类的花，问最多能有多少束花

二分答案：

通过先推答案来找是否符合要求

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<set> #include<map> #include<stack> #include<queue> #include<time.h> #define ll long long using namespace std; ll a[300100]; ll b[300100]; int n,m; ll check(ll mid){//判断是否符合要求 ll p = 1ll*mid*m; ll sum = 0; for(ll i = 1; i <= n; i++){ sum += min(1ll*a[i],mid);//如果小于mid（即答案）则其必然能被使用完全 //大于mid的最多只能使用mid个 } return sum >= p; } int main(){ ll sum = 0; ll t; scanf("%lld",&t); while(t--){ //memset(a,0,sizeof(a)); cin >> n >> m; sum=0; for(int i = 1; i <= n; i++){ scanf("%lld",&a[i]); sum += a[i]; } sort(a+1,a+1+n); //特例：如果n > m ，则不能完成要求 //相同则输出最小的数 if(m > n){ cout << 0 << endl; } else if(m == n){ cout << a[1] << endl; } else{//从0到1e14中寻找答案 ll l = 0; ll r = 1e14; ll ans = 0; while(l <= r){ ll mid = (l+r)/2; ll num = check(mid); if(num == 1){ l = mid+1; ans= mid; } else{ r = mid-1; } } printf("%lld\n",ans); } } return 0; }