D - Project Planning--二分

D - Project Planning

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

KEYENCE has NN departments, where A_iAi​ employees belong to the ii-th department (1 \leq i \leq N)(1≤i≤N). No employee belongs to multiple departments.

The company is planning cross-departmental projects. Each project will be composed of exactly KK employees chosen from KK distinct departments.

At most how many projects can be made? No employee can participate in multiple projects.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^51≤K≤N≤2×105
• 1 \leq A_i \leq 10^{12}1≤Ai​≤1012
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN KK
A_1A1​ A_2A2​ \ldots… A_NAN​

Output

Print the maximum possible number of projects.

---

Sample Input 1 Copy

Copy

3 3
2 3 4

Sample Output 1 Copy

Copy

2

There can be two projects, each composed of three employees from distinct departments.

---

Sample Input 2 Copy

Copy

4 2
1 1 3 4

Sample Output 2 Copy

Copy

4

---

Sample Input 3 Copy

Copy

4 3
1 1 3 4

Sample Output 3 Copy

Copy

2

=========================================================================

数据范围小的话优先队列贪心是很容易理解的。但本题需要二分，或许用到的这个结论是很普遍，需要特殊记住的计数问题，那就是n个小组，每组k个物体，要求组内不能重复，那么最终判定条件是所有小于等于n（大于n取等于n)的个数要 >= n*k,也就是说，只要数量够了，一定能构造出来不重复n个序列，很不好想或者去证明，只能说是一个计数结论罢了

 注意r太大会爆掉，故我们取r=1e18/k,再乘k的时候就不会爆掉了，当然128位也是很方便。

题目没一般说明我们都是在1e18内获取答案的

# include 
# include
# include
# include
# include
# include
# include
# include
# include
# include
 
 
using namespace std;
 
typedef __int128 ll;
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void print(__int128 x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
 
ll a[200000+10];
ll k,n;
 
 
bool check(ll mid)
{
 
    ll sum=0;
 
    for(int i=1;i<=n;i++)
    {
        sum+=min(mid,a[i]);
 
    }
 
    return mid*k<=sum;
}
int main()
{
 
 
 
   n=read();
   k=read();
 
     for(int i=1;i<=n;i++)
     {
       a[i]=read();
 
     }
 
 
     ll l=1,r=1e18;
 
     while(l<=r)
     {
         ll mid=(l+r)>>1;
 
         if(check(mid))
         l=mid+1;
         else
        r=mid-1;
 
 
     }
 
    print(r);
 
    return 0;
}