L-这是最难的题（二分+前缀和）

题目链接：http://acm.csust.edu.cn/problem/3024

Description

 

PC被恶龙掳走了，作为一名王子，你并打不过恶龙，所以你需要武装你的士兵一起去战胜恶龙。

但是恶龙太强了，以至于每个士兵都得有m种不同的装备才能与掳走PC的恶龙去战斗。

现在你有n种装备，每种装备有ai​件，你想知道你最多能武装多少名士兵(不要求每个士兵装备相同，只用凑出m种不同的装备，就可以获得pc的祝福)？

Input

 

先输入一个值n，再输入一个值m，接下来一行n个数，第i个数ai​代表第i个装备的数量。

Output

 

一个整数，你能够武装的最多士兵数。

Sample Input 1 

5 3
3 1 2 3 3

Sample Output 1

4

Hint

数据范围：1 <= m ， n <= 1e5, 1 <= a[i] <= 1e9

---

这个题可能就不是那么好想到了，需要转一个弯。

我们先对装备的数量排个序，记录一下排序后的前缀和，二分答案记为x，检查答案x的时候从后往前遍历，比x大的数是一定满足分配的， 当比x小的时候，我们用此时的前缀和除一下x，其值记为s，如果s与之前比x大的种类数量的和大于等于m，则该答案为可行答案，继续二分。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mac=1e5+10;
const int inf=1e9;

int a[mac],n,m;
ll sum[mac];

bool check(int x)
{
    for (int i=n; i>0; i--){
        if (a[i]<=x){
            ll ans=sum[i]/(1ll*x);
            ans+=(n-i)*1ll;
            if (ans>=m*1ll) return true;
            return false;
        }
    }
    return false;
}

int main()
{
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        scanf ("%d",&a[i]);
    sort(a+1,a+1+n);
    for (int i=1; i<=n; i++)
        sum[i]=sum[i-1]+a[i]*1ll;
    int ans=0,l=1,r=inf,mid;
    while (l<=r){
        mid=(l+r)>>1;
        if (check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf ("%d
",ans);
    return 0;
}